Thread: sum of largest sub-sequence in an array

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

Join Date
Jun 2003
Location
India
Posts
19
Rep Power
0

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. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
16
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 ... =))
3. 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...
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
16
yea .. post ur algo and I'll take a look
5. 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.
6. 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?
7. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1317
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 )
8. 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.
9. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1317
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."
10. 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;         }     }  ```
11. 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!
12. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

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