GATE CS 2019 Q25 — Algorithm Design: Greedy Techniques

This is the classic Maximum Subarray Sum problem. We can solve this efficiently in $O(n)$ time using Kadane's Algorithm.

Kadane's Algorithm Steps

Let $A$ be the given array of size 14:

$$A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]$$

We maintain two variables:

• current_max: The maximum subarray sum ending at the current position.
• global_max: The overall maximum subarray sum found so far.

We iterate through the array from index $0$ to $13$ using the recurrence:

$$\text{current\_max}[k] = \max(A[k], \text{current\_max}[k-1] + A[k])$$

The maximum subarray sum is achieved by the subarray from index $2$ to $11$:

$$A[2 \dots 11] = [6, 3, -1, -2, 13, 4, -9, -1, 4, 12]$$

$$\text{Sum} = 6 + 3 - 1 - 2 + 13 + 4 - 9 - 1 + 4 + 12 = 29$$

Thus, the maximum of $S(i,j)$ is 29.