
sum of largest subsequence in an array
given an array of n elements , how can 1 find the subsequence that yields the maximum sum.. Note that negative numbers are
present in the array.
Thanks

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

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

yea .. post ur algo and I'll take a look
July 15th, 2003, 12:01 AM

aah yogi,
got struck in a couple of other things.. cudnt pay much attention to algo's and my preparation for jobseeking..
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 subsequence
but it doesnt work for nos < 0.
pardon me if u'd problem reading d algo as i prefer to write 'C' style algos.
April 13th, 2004, 04:59 PM

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?
April 16th, 2004, 06:41 PM

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 )
April 18th, 2004, 08:38 PM

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.
April 23rd, 2004, 12:07 AM

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."
August 6th, 2004, 04:22 AM

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 0indexed. 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 subarray.
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 subarray 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 subarray. 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[$i1];
if ($x[$i]$minv>=$maxv) {
$maxv = $x[$i]$minv;
$maxi1 = $mini+1;
$maxi2 = $i;
}
if ($x[$i]<$minv) {
$minv = $x[$i];
$mini = $i;
}
}
April 22nd, 2006, 01:25 PM

thank you basarane for writing such a nice algorithm
you rock!
April 22nd, 2006, 03:07 PM

I think basarane has left the building, considering he hasn't posted since August 6, 2004.