Question 35

The given array of 14 elements is:

We compute the maximum subarray sum using Kadane's algorithm, maintaining current_sum and max_so_far:

• $k = 0, A[0] = -5$: $\text{curr} = -5, \text{max} = -5$
• $k = 1, A[1] = -10$: $\text{curr} = -10, \text{max} = -5$
• $k = 2, A[2] = 6$: $\text{curr} = 6, \text{max} = 6$
• $k = 3, A[3] = 3$: $\text{curr} = 6 + 3 = 9, \text{max} = 9$
• $k = 4, A[4] = -1$: $\text{curr} = 9 - 1 = 8, \text{max} = 9$
• $k = 5, A[5] = -2$: $\text{curr} = 8 - 2 = 6, \text{max} = 9$
• $k = 6, A[6] = 13$: $\text{curr} = 6 + 13 = 19, \text{max} = 19$
• $k = 7, A[7] = 4$: $\text{curr} = 19 + 4 = 23, \text{max} = 23$
• $k = 8, A[8] = -9$: $\text{curr} = 23 - 9 = 14, \text{max} = 23$
• $k = 9, A[9] = -1$: $\text{curr} = 14 - 1 = 13, \text{max} = 23$
• $k = 10, A[10] = 4$: $\text{curr} = 13 + 4 = 17, \text{max} = 23$
• $k = 11, A[11] = 12$: $\text{curr} = 17 + 12 = 29, \text{max} = 29$
• $k = 12, A[12] = -3$: $\text{curr} = 29 - 3 = 26, \text{max} = 29$
• $k = 13, A[13] = 0$: $\text{curr} = 26 + 0 = 26, \text{max} = 29$

The maximum contiguous subsequence sum is $29$, achieved by subarray from index 2 to index 11: