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

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    225

    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. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Hacker MeTh0Dz's Avatar
    Join Date
    Oct 2008
    Posts
    111
    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. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    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. #5
    Hacker MeTh0Dz's Avatar
    Join Date
    Oct 2008
    Posts
    111
    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. #6
    Hacker MeTh0Dz's Avatar
    Join Date
    Oct 2008
    Posts
    111
    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;
    }
    Last edited by MeTh0Dz; 10-25-2008 at 02:31 PM. Reason: Now works for all negative arrays

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    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. #8
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Quote Originally Posted by MeTh0Dz View Post
    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. #9
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    But mine is a linear solution? and hence very efficient???except poor variable names and yeah i meant sub-array with maximum sum
    Last edited by chottachatri; 10-25-2008 at 08:12 PM.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Except the answer is 16 (5+-2+3+-1+2+-1+10).

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Quote Originally Posted by tabstop View Post
    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. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by chottachatri View Post
    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. #13
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Ok you changed the problem definition altogether. Ok i will post solution for that soon
    Last edited by chottachatri; 10-26-2008 at 02:58 AM.

  14. #14
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    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. #15
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    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 subscribe to a feed

Similar Threads

  1. ?? with trying to sum numbers
    By Babs21 in forum C Programming
    Replies: 1
    Last Post: 09-16-2007, 03:58 PM
  2. Writing unique numbers to an array
    By yardy in forum C Programming
    Replies: 6
    Last Post: 12-27-2006, 09:15 PM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. Finding largest element in array
    By Chaplin27 in forum C++ Programming
    Replies: 2
    Last Post: 04-12-2005, 09:18 PM
  5. strange numbers, while loops questionable?
    By exluddite in forum C++ Programming
    Replies: 8
    Last Post: 05-06-2004, 11:11 AM