max-subarray.md (1130B)
1 +++ 2 title = "Max subarray" 3 template = "page-math.html" 4 +++ 5 6 # Max subarray 7 8 Problem 9 10 Assume array of integers. Give maximum sum of elements of a contiguous subarray. 11 12 A = [-6, 2, -4, 1, 3, -1, 5, -1] 13 14 Solution 15 Create a table containing arrays A and a new array B. 16 Initialise first element of B with max(A[1], 0): 17 18 <table> 19 <tr><td>A</td><td>-6</td><td>2</td><td>-4</td><td>1</td><td>3</td><td>-1</td><td>5</td><td>1</td></tr> 20 <tr><td>B</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr> 21 </table> 22 23 For each cell B: 24 25 - B[i] = max{ B[i-1]+A[i], 0 } 26 - m = max{ B[i], m } 27 28 <table> 29 <tr><td>A</td><td>-6</td><td>2</td><td>-4</td><td>1</td><td>3</td><td>-1</td><td>5</td><td>-1</td></tr> 30 <tr><td>B</td><td>0</td><td>2</td><td>0</td><td>1</td><td>4</td><td>3</td><td>8</td><td>7</td></tr> 31 </table> 32 33 m holds the highest sum: 34 m=8 35 36 To find subarray, go back from m until you find a 0. 37 [1,3,-1,5] 38 39 Complexity 40 The brute force algorithm is is in O(n2) 41 Divide and conquer is in O(nlogn) 42 DP brings it down to O(n). 43 44 $S(i) = \begin{cases} 45 A[i] & \text{if } i = 0\\\\ 46 \max {S(i-1)+A[i], A[i]} & otherwise \end{cases}$