# Maximum Value Contiguous Subsequence [closed]

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?

## closed as unclear what you're asking by D.W.♦, Luke Mathieson, David Richerby, Wandering Logic, JuhoMay 26 '14 at 13:39

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• There is no such thing as the intended solution, and if there is, we have no way of knowing it. There are only correct solutions and wrong solutions. You indicate that you're not sure whether your solution is correct. I suggest you try harder convincing yourself that your solution is correct. – Yuval Filmus May 15 '14 at 14:41
• You don't even specify what your algorithm will return. So this can't be a correct solution. – FrankW May 15 '14 at 15:36
• @Yuval Filmus are you hinting that my solution is correct? – HaloKiller May 15 '14 at 15:43
• @FrankW let's say we return the sequence itself – HaloKiller May 15 '14 at 15:44
• @Trinarics That is not a valid solution, unless it happens to be ordered. – FrankW May 15 '14 at 15:49

Here is another suggestion. Given the original array $A_1,\ldots,A_n$, define a new array $B_0, B_1,\ldots,B_n$ by $$B_i = \sum_{j=1}^i A_j.$$ This is useful since $$\sum_{j=i_1}^{i_2} A_j = B_{i_2} - B_{i_1-1}.$$ So now we want to find the maximum value of $B_{i_2} - B_{i_1-1}$. The idea is to scan the array from left to right, keeping track of the optimal choice of $i_1$ at any given moment. I will let you fill in the details.