Printable View
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;
}
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
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;
}
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?
When he said consecutive integers I assumed that he meant 2 consecutive integers.
I'll do an implementation that will work for any amount.
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.
Here is my solution, it could probably be optimized, but nonetheless it works.Code:{-1, -3, -5, -10, 5, -2, 3, -1, 2, -1, 10, -20};
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;
}
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.
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!Quote:
Originally Posted by MeTh0Dz
So where's the confusion dude??my solution works for every case.
But mine is a linear solution? and hence very efficient???except poor variable names and yeah i meant sub-array with maximum sum
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?Quote:
Originally Posted by tabstop
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.Quote:
Originally Posted by chottachatri
Ok you changed the problem definition altogether. Ok i will post solution for that soon
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;
}
Not quite. Try it with this data:
Your program gives 100 but the correct answer is 103.Code:int a[]={ -3, 100, -4, -2, 9, -63, -200, 55};
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.
No.Quote:
Originally Posted by chottachatri
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.
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.