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

Originally Posted by chottachatri

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.

No.

There are tons of cases in which your first solution won't work. So this entire paragraph was irrelevant. Also just by looking at your newest solution it appears that you haven't added support for all negative arrays.

Review how I did it and then you'll understand a 'working' solution.

Regardless of the efficiency of my code, it works in ALL cases.

While on the otherhand we have your code which doesn't work in a ton of cases. The point of my code was to give you an example of how to properly implement the algorithm.

No, i want the solution that works in ALL cases as well as is the most efficient. Hence, i am posting my solution that will work in any case( well! almost!any case ). Removed the bugs that were prevalent in my previous solution. Use this as a guide to develop your own algorithm. You won't find my code anywhere on the net(or in any book for that matter). Hence it's not a blatant lift

Please test it and tell me if any bugs are still there

Code:

#include <stdio.h>

//To Find Largest Consecutive Sum Of Numbers in Array

int main(void)
{
 int a[]={-3, 100, -4, -2, 9, -63, -200, 55};
 int max,q,i,n=8,max_neg=-32767;
 max=-32767;
 for(i=0;i<n;i++)
 {
	q=0;
	while(a[i]<0 && i<n)
	{
		q+=a[i];
		if(max_neg<a[i])
			max_neg=a[i];
		i++;
	}
   if(max<0 && i==n)  //all negative numbers in array
		max=max_neg;
   else if((max<0 || (max+q<0 && a[i]>max)) && i<n)  //start to find new sub array
		max=a[i];
   else if(q+max>0 && i<n)   //numbers following max are to be taken into account
		max=max+q+a[i];
 }
 printf("The Largest Sum Of Consecutive Numbers is %d",max);
 return 0;
}

This is what I came up with. I haven't found a problem with it, maybe you guys can.

Code:

int maxConsecutiveNumbers(int length, int a[]) {
    
    int currentMax = 0;
    int leftSide = 0;
    
    //scan the list
    for (int i=0; i<length; i++) {
        
        if (a[i] < 0) {//if it is negative
            if (abs(a[i]) >= leftSide) {
                leftSide = 0;
            } else if (abs(a[i]) <= leftSide) {
                leftSide += a[i];
            }
            
        } else {
            leftSide += a[i];
        }
        
        if (leftSide > currentMax) {
            currentMax = leftSide;
        }        
    }
    
    return currentMax;
}