Given an array of integers. Find the biggest sum subsequence.
For example: a={2, -9, 4,6, 3, -2, 5, 5, -10}
Largest subsequence is 4, 6, 3, -2, 5, 5.
Soln:
http://en.wikipedia.org/wiki/Kadane%27s_Algorithm
WIth this you get where the larges sum ends.
Find the starting point as well.
a={2, -9, 4, 6, 3, -2, 5, 5, -10}
ReplyDeleteLarge sum is 21
Large sum ending index is (lsei) = 7 (Its value is last 5 in the array)
Now subtract a[lsei], a[lsei-1] a[lsei-2]etc.. from large sum(21) till the result is zero. When the result is zero, the index lsei - i gives the large sum start index.