Like Tree1Likes

To Find Largest Consecutive Sum Of Numbers In 1D Array

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

  1. #16
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    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."

  2. #17
    Hacker MeTh0Dz's Avatar
    Join Date
    Oct 2008
    Posts
    111
    Quote Originally Posted by chottachatri View Post
    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.

  3. #18
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    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.

  4. #19
    Hacker MeTh0Dz's Avatar
    Join Date
    Oct 2008
    Posts
    111
    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.

  5. #20
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > 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!

  6. #21
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    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;
    }

  7. #22
    Registered User
    Join Date
    Jul 2011
    Posts
    1
    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;
    }

  8. #23
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    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.
    Salem likes this.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

Page 2 of 2 FirstFirst 12
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, 08: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21