#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0

    Question sum of largest sub-sequence in an array


    given an array of n elements , how can 1 find the sub-sequence that yields the maximum sum.. Note that negative numbers are
    present in the array.

    Thanks
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    haha .. theres an o(n^3) algo, an o(n^2) algo, a clever o(nlogn) devide and conquer algo, but theres also a very simple, but very very clever o(n) one.

    not givin it to ya though cuz u said i wasn't lazy

    heheheheheh
    lazy bastard gets the last laugh ... =))
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    hey yogi,
    i have figured out the 0(n) and the divide and conquer 1 also.. but the ? is for negative nos.
    my algo works only for positive nos.
    i can post u my algos if u wish...
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    yea .. post ur algo and I'll take a look
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    aah yogi,
    got struck in a couple of other things.. cudnt pay much attention to algo's and my preparation for job-seeking..

    my code..
    assuming integers in the array...
    int localsum = 0;
    int globalsum = 0;
    for (i = 0; i < n; ++i)
    {
    localsum +=a[i];

    if (localsum > global)
    globalsum = localsum;
    else if (localsum <0)
    localsum = 0;
    }

    at the end, globalsum will have the largest sum of the sub-sequence
    but it doesnt work for nos < 0.


    pardon me if u'd problem reading d algo as i prefer to write 'C' style algos.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2004
    Posts
    1
    Rep Power
    0
    How could I turn this into an O(n) alogrithm that looks for 2 integers that add up to a set amount instead of the maximum?
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    Originally Posted by locopuyo
    How could I turn this into an O(n) alogrithm that looks for 2 integers that add up to a set amount instead of the maximum?
    I'm not sure how to make a guaranteed O(n) algorithm, but an expected O(n) algorithm is easy: go through the array and hash each element into a hash table, and also check if the number you need to add to that number to make it add up the the set amount is in the hash table already. By the time you reach the end of the array, you'll either have some pair that adds to the number, or you'll be sure that there aren't any.

    That's not guaranteed to be linear because for practical purposes, hash tables are only expected to have constant time insertion/access performance.

    It's surprising that the solution to the original problem of this thread was never posted. I don't think the O(n) algorithm requires any extreme cleverness (don't know what lazy_yogi was going on about )
  14. #8
  15. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Well, I wasn't sure I understood the question, because if I did the answer would be trivial. Find the smallest end, the rest is the subsequence with the greatest sum.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    I took it to mean "given an array A, find indices i, j (i <= j) for which the sum

    A[i] + A[i + 1] + A[i + 2] + ... + A[j - 1] + A[j]

    is maximized."
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2004
    Posts
    1
    Rep Power
    0

    Simple O(n) algorithm


    Yesterday one of my friends ask for a linear algorithm for this problem. I think that the following algorithm solves the problem in linear time. But it should be checked. It is written in php and $x is the array of numbers and $n is the number of elements in the array. Array is assumed to be 0-indexed. -9999999999 is used for -Inf and it should be changed with true -Inf constant. $maxv is the maximum sum and $maxi1 and $maxi2 is the start and end indices of the sub-array.

    The idea behind the algorithm is as follows:
    It uses cumulative sum instead of the original array. Then at each index, it calculates the difference of the value at that index and the smallest value before that index. The maximum sub-array must have this value maximized. Two loops are merged into a single loop. After one pass over the numbers, we have the largest sum and boundary indices of the sub-array. So dynamic programming method is used.

    Please check it and let me know if the algorithm is right.

    PHP Code:
        $mini = -1;
        
    $minv 0;
        
    $maxi1 0;
        
    $maxi2 0;
        
    $maxv = -9999999999;
        
        for (
    $i=0;$i<$n;$i++) {
            if (
    $i>0)
                
    $x[$i] += $x[$i-1];
            if (
    $x[$i]-$minv>=$maxv) {
                
    $maxv $x[$i]-$minv;
                
    $maxi1 $mini+1;
                
    $maxi2 $i;
            }
            if (
    $x[$i]<$minv) {
                
    $minv $x[$i];
                
    $mini $i;
            }
        } 
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2006
    Posts
    1
    Rep Power
    0
    thank you basarane for writing such a nice algorithm
    you rock!
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    I think basarane has left the building, considering he hasn't posted since August 6, 2004.

IMN logo majestic logo threadwatch logo seochat tools logo