Problem
Assume array of integers. Give maximum sum of elements of a contiguous subarray.
A = [-6, 2, -4, 1, 3, -1, 5, -1]
Solution Create a table containing arrays A and a new array B. Initialise first element of B with max(A[1], 0):
| A | -6 | 2 | -4 | 1 | 3 | -1 | 5 | 1 |
| B | 0 |
For each cell B:
| A | -6 | 2 | -4 | 1 | 3 | -1 | 5 | -1 |
| B | 0 | 2 | 0 | 1 | 4 | 3 | 8 | 7 |
m holds the highest sum: m=8
To find subarray, go back from m until you find a 0. [1,3,-1,5]
Complexity The brute force algorithm is is in O(n2) Divide and conquer is in O(nlogn) DP brings it down to O(n).
$S(i) = \begin{cases} A[i] & \text{if } i = 0\\ \max {S(i-1)+A[i], A[i]} & otherwise \end{cases}$