This problem can be solved in O(n). Just by looking at your code and some code that solves it O(n), I can tell yours doesn't. Even if it does, the code is so ugly and jaded that it's impossible to tell.
This is a discussion on To Find Largest Consecutive Sum Of Numbers In 1D Array within the C Programming forums, part of the General Programming Boards category; This problem can be solved in O(n). Just by looking at your code and some code that solves it O(n), ...
This problem can be solved in O(n). Just by looking at your code and some code that solves it O(n), I can tell yours doesn't. Even if it does, the code is so ugly and jaded that it's impossible to tell.
"What's up, Doc?"
"'Up' is a relative concept. It has no intrinsic value."
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.
i'll do a review later as i think i got it and secondly your code is very inefficient. The optimum solution to this is you should have used a single pass through the array.
Last edited by chottachatri; 10-26-2008 at 08:58 PM.
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.
> it works in ALL cases.
Except on my machine where the range of signed short integers is -6 to 7 . Try and avoid magic numbers... that's what limits.h is for!
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; }
The last post on this thread was in 2008. It is now 2011. If you have a question start a new thread, otherwise please don't bump old threads.