Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, 2, 13, 4, -9, -1, 4, 12, -3, 0]. Determine the maximum of S(i, j), where S(i, j) = sum_{k=i}^{j} A[k] and 0 <= i <= j <= 13. (Divide and conquer approach may be used.) Answer: ___________

GATE 2019 · Algorithms · Algorithm Design · medium

Answer: The maximum of S(i,j) is 33 (achieved by the subarray A[2..11] = [6, 3, -1, 2, 13, 4, -9, -1, 4, 12]).

1. Apply Kadane's algorithm: Trace through A = [-5,-10,6,3,-1,2,13,4,-9,-1,4,12,-3,0]: i=0: A=-5, meh=-5, msf=-5 i=1: A=-10, meh=-10, msf=-5 (restart: -10 < -5+-10=-15, use -10) i=2: A=6, meh=6, msf=6 (restart: 6 > -10+6=-4) i=3: A=3, meh=9, msf=9 i=4: A=-1, meh=8, msf=9 i=5: A=2, meh=10, msf=10 i=6: A=13, meh=23, msf=23 i=7: A=4, meh=27, msf=27 i=8: A=-9, meh=18, msf=27 i=9: A=-1, meh=17, msf=27 i=10: A=4, meh=21, msf=27 i=11: A=12, meh=33, msf=33 i=12: A=-3, meh=30, msf=33 i=13: A=0, meh=30, msf=33
2. Verify the maximum subarray: S(2,11) = 6 + 3 - 1 + 2 + 13 + 4 - 9 - 1 + 4 + 12 = (6+3+2+13+4+4+12) - (1+9+1) = 44 - 11 = 33. This matches the Kadane's result.