Maximum Value Contiguous Subsequence I have stumbled upon this problem online:


  Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i)... > A(j) for which the sum of elements in the subsequence is maximized.


Now my solution is so:
I assume that the sequence is stored in an array.
We need 2 arrays under the original array, one is a flag array A and the other is a real number array B.

Take the first element as the subsequence we are searching for, put a 1 under it in A, and put the value of the element in it's index in B (which is right under it's index in A).
Go to the next element.
If it isn't negative, put a 1 under it in A, and put the sum of that element and the element before him in B.
If it's negative, put a 0 under it in A, and go to the next element, starting a new subsequence.

The complexity is O(n) time because I run on the whole sequence once.

Example:

Sequence: 4 33 -24 3 4 2 -5 6 19 -11 32 40 -30 5 6
Array A:  1  1   0 1 1 1  0 1  1   0  1  1   0 1 1
Array B:  4 37  13 3 7 9  4 6 19   8 32 70  40 5 11

My question is: is that the wanted solution? and does it really run in O(n) time?
Your algorithm does not yield the solution. An extension of your algorithm that follows will provide a solution.
You need to mark the extremes of consecutive 1's in the flag array (an obvious observation ). For example, the flag array is 1111101111 then you need to mark 0,5,9 indices (zero based) and for every pair of extremes you need to find the difference computed in prefix sum array. The number of marker indices are of the order of n. So number of pairs are of the order n^2.