Program to find the largest sum of contiguous integers in
the array. O(n)
Answer Posted / jjaspirin
I came to this website looking for the solution and finally
ended up writing it myself. Hope this is useful for someone
else.
Here is a working solution. Set the array "a" and N_ELEMENTS
accordingly. Some cases are not covered but should be an
easy fix.
#include <stdio.h>
#define N_ELEMENTS 7
int main() {
int a[N_ELEMENTS] = {-1, 2, -3, 2, 0, 5, -11 }; // if
you change the array, make sure you change N_ELEMENTS
int i = 0;
while(a[i] < 0 && i<N_ELEMENTS) {
i++;
}
if (a[i] < 0) {
printf ("DEBUG: array with only negative numbers.
Print the smallest negative number as the sum and we are
done.\n");
}
int sum_p=0, sum_n = 0;
int largest_sum = 0;
while (i<N_ELEMENTS) {
if (a[i] > 0) {
sum_p += a[i];
}
else {
sum_n += a[i];
}
if (sum_p+sum_n > largest_sum) {
largest_sum = sum_p + sum_n;
}
if (sum_p+sum_n <= 0) {
// find the next positive number
while(a[i] < 0 && i<N_ELEMENTS) {
i++;
}
if (a[i] < 0 || i == N_ELEMENTS) {
break;
}
sum_p = 0;
sum_n = 0;
} else {
i++;
}
}
printf ("DEBUG: The largest consecutive sum = %d\n",
largest_sum);
}
| Is This Answer Correct ? | 3 Yes | 2 No |
Post New Answer View All Answers
Sir... please give some important coding questions asked by product companies..
How can I Create a C program in splitting set of characters to specific subsets. Example: INPUT SET OF CHARACTERS: Therefore, my dear brothers and sisters, stand firm. Let nothing move you. Always give yourselves fully to the work of the Lord, because you know that your labor in the Lord is not in vain. SPLIT INTO HOW MANY CHARACTERS PER SUBSETS: 10 OUTPUT: Therefore, my dear b rothers an d sisters, stand fir m. Let not hing move you. Alway s give you rselves fu lly to the work of t he Lord, b ecause you know that your labo r in the L ord is not in vain.
create a C-code that will display the total fare of a passenger of a taxi if the driver press enter,the timer will stop. Every 10 counts is 2 pesos. Initial value is 25.00
write a function to give demostrate the functionality of 3d in 1d. function prototye: change(int value,int indexX,int indexY,int indexZ, int [] 1dArray); value=what is the date; indexX=x-asix indexY=y-axis indexZ=z-axis and 1dArray=in which and where the value is stored??
Write a program to model an exploding firecracker in the xy plane using a particle system
What is the match merge ? compare data step match merge with proc sql merge - how many types are there ? data step vs proc sql
Write a routine to implement the polymarker function
why do you use macros? Explain a situation where you had to incorporate macros in your proc report? use a simple instream data example with code ?
How to palindrom string in c language?
What is full form of PEPSI
How do you verify if the two sentences/phrases input is an anagram using predefined functions in string.h and by using arrays?
write a simple calculator c program to perform addition, subtraction, mul and div.
Develop a routine to reflect an object about an arbitrarily selected plane
can you use proc sql to manpulate a data set or would u prefer to use proc report ? if so why ? make up an example and explain in detail
how to create a 3x3 two dimensional array that will give you the sums on the left and bottom columns