Project ForgeAlgorithms
Dynamic Programming & Greedy Algorithms
GATE 2019
Hard
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)=Σ(k=i to j) A[k]. Determine the maximum of S(i,j), where 0≤i≤j<14. (Divide and conquer / Kadane's approach may be used.)
29
Explanation
Running Kadane's algorithm (current = max(A[k], current+A[k]), best = max(best,current)) across the array, the running sum peaks at index 11 (value 12), having accumulated the subarray from index 2 to 11: 6+3-1-2+13+4-9-1+4+12 = 29 — the maximum subsequence sum.
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.