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
The maximum sum contiguous subarray starts at 6 and ends at 12: $6+3-1-2+13+4-9-1+4+12=29$.