https://leetcode.com/problems/maximum-subarray/
Each question in DP seems to be different, but the ideas are consistent.

Question:

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

If you want to exhaust all subarrays, the time complexity reaches to O(n2). This is obviously Time Limit Exceeded, but I did…= =!

Stupid boy…

Assume it begins from one item ``, when add a item to the array, you should consider if the previous item is a positive number.
If it’s a positive number, then we can calculate the sum of these two number, two good brother.
Otherwise, if the previous item is a negative number, these two are not good brother, we will not calculate the sum.

Attention, `previous number` can also be considered as `previous sum`, understand? Now we have completed the decomposition of the goal problem to sum problem:

`maxSubArray(A, i) = A[i] + maxSubArray(A, i - 1) > 0 : maxSubArray(A, i - 1) : 0`

`i` as the array size increases, `maxSubArray(A, i - 1)` means the previous sum.

We can also reduse the complexity of space.