The GATE Grind

GATE 2019 CS – Question 35

Algorithms · Divide-and-Conquer · 1 mark · Numerical answer

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):

elementbest ending hereoverall best
-5-5-5
-10-10-5
666
399
-189
-269
131919
42323
-91423
-11323
41723
122929
-32629
02629

The maximum is **29** (from the element 6 to the element 12).

More Divide-and-Conquer questions

All Divide-and-Conquer questions →