Largest contiguous sum [duplicate]

This question already has answers here: 开发者_开发技巧 Closed 11 years ago.

Possible Duplicate:

Find the maximum interval sum in a list of real numbers

Below is my dp expression to solve this:

lcs[i] = { max(lcs[i-1] + x[i], x[i])}

where lcs[i] is the longest contiguous sum till index i and also including element x[i]. However, i dont know why we define lcs[i] to also include x[i]. Can't we just define lcs[i] as the longest contiguous sum till index i.

---

You can't just define lcs[i] as lcs[i-1]+x[i] because of the possibility of negative numbers in the list.

Consider the list x={-1, 1}.

lcs[0] = -1
lcs[1] = max(-1+1,1) = 1 != -1+1

If your list was strictly non-negative, then yes, you could define lcs[i]=lcs[i-1]+x[i]. But notice that this recursive definition translates directly to a sum over all x[i]. This agrees to the intuitive notion that the maximum contiguous sum of a list of positive numbers is simply the sum of all the elements in the list.