GATE 2019 CS – Question 35
Consider a sequence of 14 elements: $A=[-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0]$. The subsequence sum $S(i,j)=\sum_{k=i}^{j}A[k]$. Determine the maximum of $S(i,j)$, where $0\le i\le j<14$. (Divide and conquer approach may be used.)
Answer: ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 29
Explanation
This is the **maximum contiguous subarray sum** (Kadane / divide and conquer). Array: $-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0$.
Run Kadane's algorithm (best sum ending here, overall best):
| element | best ending here | overall best |
|---|---|---|
| -5 | -5 | -5 |
| -10 | -10 | -5 |
| 6 | 6 | 6 |
| 3 | 9 | 9 |
| -1 | 8 | 9 |
| -2 | 6 | 9 |
| 13 | 19 | 19 |
| 4 | 23 | 23 |
| -9 | 14 | 23 |
| -1 | 13 | 23 |
| 4 | 17 | 23 |
| 12 | 29 | 29 |
| -3 | 26 | 29 |
| 0 | 26 | 29 |
The maximum is **29** (from the element 6 to the element 12).