# To Find Largest Consecutive Sum Of Numbers In 1D Array

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 10-25-2008
chottachatri
To Find Largest Consecutive Sum Of Numbers In 1D Array
Hello,
i wrote a program .Please analyse it and if any bug or any optimisation required then please suggest

Code:

```#include <stdio.h> //To Find Largest Consecutive Sum Of Numbers in Array int main(void) {  int a[]={-1,-3,-5,-10,5,10,-20};  int p,q,i,n=8;  p=q=a[0];  for(i=1;i<n;i++)  {         if(a[i]>0 && p>0)                 p+=a[i];         else         {                 if(p>q)                         q=p;                 p=a[i];         }  }  if(p>q)         q=p;  printf("The Largest Sum Of Consecutive Numbers is %d",q);  return 0; }```
• 10-25-2008
matsp
Better names of variables would probably be a good idea.

"n" should probably be const, and then used to set the size of the array (or initialized based on the size of the array), since it correlates to that.

I don't know what your specification is, but if you do not have a requirement that says "skip negative numbers", then comparing > 0 will not make a benefit.

--
Mats
• 10-25-2008
MeTh0Dz
Try this out for your for loop.

Where i is just an index;
Where len is the length of the array;
Where big is just a variable that holds the biggest consecutive sums you've reached so far.
Where array is the integer array.

Code:

```big = 0; for (i = 0; i < len - 1; i++) {         array[i] + array[i + 1] > big ? (big = array[i] + array[i + 1]) : 0; }```
• 10-25-2008
arpsmack
Its great except for the tiny little fact that it doesn't work.

Try this: 5, 6, 0, -5, 10
The max sum is 5+6+0-5+10 = 16

• 10-25-2008
MeTh0Dz
When he said consecutive integers I assumed that he meant 2 consecutive integers.

I'll do an implementation that will work for any amount.
• 10-25-2008
MeTh0Dz
The original implementation doesn't work for all cases.

However mine does.

If you want an example of when mine works and the original doesn't try this number set.

Code:

`{-1, -3, -5, -10, 5, -2, 3, -1, 2, -1, 10, -20};`
Here is my solution, it could probably be optimized, but nonetheless it works.

Where the same stuff applies from above with these additions.
Where j is an additional index.
Where back_to is an integer 'value-holder'.
Where temp is another 'value-holder'.

Note...... big must be initialized to -32768.

(This assumes that we are using signed short integers)
Code:

```for (i = 0; i < len - 1; i++) {         temp = 0;         back_to = -32768;         for (j = i; j < len; j++) {                 temp += array[j];                 if (temp > back_to) back_to = temp;         }         if (back_to > temp) temp = back_to;         if (temp > big) big = temp; }```
• 10-25-2008
arpsmack
Yeah, his choice of wording was poor, and I'm not even sure it makes sense.

I parse it as either:

largest (consecutive sum) of numbers
or
largest consecutive (sum of numbers)

"consecutive sum" doesn't seem to make sense by itself, so that can't be it. But "sum of numbers" is singular, and so its not likely that he meant to say "consecutive (sum of numbers)". You don't often hear the word consecutive followed by a singular noun.

So I took the liberty of interpreting it as "the sub-array with the largest sum", which seems to be a fairly popular problem as of late. At the very least its more interesting than the largest sum of 2 consecutive numbers.

ANYWAY...

I'll take your word that your solution works; however it runs in O(n^2). Now try to find the linear solution.

Lets see something that will scale up to a couple million elements or more.
• 10-25-2008
chottachatri
Quote:

Originally Posted by MeTh0Dz
The original implementation doesn't work for all cases.

However mine does.

[CODE]{-1, -3, -5, -10, 5, -2, 3, -1, 2, -1, 10, -20};

So where's the confusion dude??my solution works for every case.
• 10-25-2008
chottachatri
But mine is a linear solution? and hence very efficient???except poor variable names and yeah i meant sub-array with maximum sum
• 10-25-2008
tabstop
Except the answer is 16 (5+-2+3+-1+2+-1+10).
• 10-26-2008
chottachatri
Quote:

Originally Posted by tabstop
Except the answer is 16 (5+-2+3+-1+2+-1+10).

Whose Answer is 16?whose program did you execute?mine or that another dude's program?
When you run my program i got 10 and which is the correct one according to my requirements!
• 10-26-2008
tabstop
Quote:

Originally Posted by chottachatri
Whose Answer is 16?whose program did you execute?mine or that another dude's program?
When you run my program i got 10 and which is the correct one according to my requirements!

The answer to the question is 16. I showed you which consecutive numbers in the list add up to 16, and 16 is definitely larger than 10.
• 10-26-2008
chottachatri
Ok you changed the problem definition altogether. Ok i will post solution for that soon
• 10-26-2008
chottachatri
Ok i came up with this linear solution. Please check it whether it works with all data sets or what problems is it still suffering from

Code:

```#include <stdio.h> //To Find Largest Consecutive Sum Of Numbers in Array int main(void) {  int a[]={-1,-3,-5,-10,5,-2,3,-1,2,-1,10,-2};  int max_sum,temp_sum,i,n=12,t;  temp_sum=max_sum=a[0];  for(i=1;i<n;i++)  {         if(a[i]>0)                 temp_sum+=a[i];         else         {                 t=0;                 while(a[i]<0 && i<n)                 {                         t+=a[i];                         i++;                 }                 if(temp_sum+t>0)                 {                         temp_sum=temp_sum+t+a[i];                         if(temp_sum>max_sum)                                 max_sum=temp_sum;                 }                 else if(i<n)                         temp_sum=a[i];         }  }  if(temp_sum>max_sum)         max_sum=temp_sum;  printf("The Largest Sum Of Consecutive Numbers is %d",max_sum);  return 0; }```
• 10-26-2008
nonoob
Not quite. Try it with this data:
Code:

`int a[]={ -3, 100, -4, -2, 9, -63, -200, 55};`