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

1. ## 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;
}```

2. 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

3. 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;
}```

4. 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

What does your program say?

5. When he said consecutive integers I assumed that he meant 2 consecutive integers.

I'll do an implementation that will work for any amount.

6. 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;
}```

7. 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.

8. 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};
Who said so it doesn't work? just check it out dude first is -1 and then -3 so adding any negative number(-3) to a negative number(-1) is going to make it a tinier number than our original number (-1). Hence we don't add it in similar way we traverse till -10 and then we come to 5 now 5 is greater than our -1 so we take our base now as 5 and thereafter adding any negative number to our base will make it a tinier number we again dont add -2. Then we come to 3? now compare 3 with 5. It's smaller than 5 so we dont need to change our base. Then again negative so again no addition then 2 which is smaller and then negative so no addition. Then 10 we now choose 10 as our base as 10 is greater than 5 and then again negative. So adding -20 to 10 will make our base smaller so no addition. Had there been 20 instead of -20 in the last number. Our consecutive sum would have been 30 since a[i] >0 so we would add it to our base 10 and hence 30 but since it's negative we don't add it. Hence answer is 10!

So where's the confusion dude??my solution works for every case.

9. But mine is a linear solution? and hence very efficient???except poor variable names and yeah i meant sub-array with maximum sum

10. Except the answer is 16 (5+-2+3+-1+2+-1+10).

11. 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!

12. 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.

13. Ok you changed the problem definition altogether. Ok i will post solution for that soon

14. 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;
}```

15. Not quite. Try it with this data:
Code:
`int a[]={ -3, 100, -4, -2, 9, -63, -200, 55};`
Your program gives 100 but the correct answer is 103.

Popular pages Recent additions