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=ij A[k] . Determine the maximum of S(i,j), where 0 i j < 14. (Divide and conquer approach may be used.) Answer: …

Official answer: 29. Explanation: We need to find the maximum subarray sum of the array: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0] Using Kadane's algorithm (or the Divide-and-Conquer maximum subarray sum approach): 1. At index 0 (A[0] = -5): current\max = -5, global\max = -5 2. At index 1 (A[1] = -10): current\max = -10, global\max = -5 3. At index 2 (A[2] = 6): current\max = 6, global\max = 6 4. At index 3 (A[3] = 3): current\max = 9, global\max = 9 5. At index 4 (A[4] = -1): current\max = 8, global\max = 9 6. At index 5 (A[5] = -2): current\max = 6, global\max = 9 7. At index 6 (A[6] = 13): current\max = 19, global\max = 19 8. At index 7 (A[7] = 4): current\max = 23, global\max = 23 9. At index 8 (A[8] = -9): current\max = 14, global\max = 23 10. At index 9 (A[9] = -1): current\max = 13, global\max = 23 11. At index 10 (A[10] = 4): current\max = 17, global\max = 23 12. At index 11 (A[11] = 12): current\max = 29, global\max = 29 13. At index 12 (A[12] = -3): current\max = 26, global\max = 29 14. At index 13 (A[13] = 0): current\max = 26, global\max = 29 The contiguous subarray giving this maximum is from index i = 2 to j = 11: [6, 3, -1, -2, 13, 4, -9, -1, 4, 12] Sum = 6 + 3 - 1 - 2 + 13 + 4 - 9 - 1 + 4 + 12 = 29

Algorithms · Divide and Conquer

Official IIT answer key · IIT Madras · Audited Aug 2026

Take topic test

GATE CSE 2019 Q25 · NAT · 1 mark

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: _______.

Numerical answer

Enter a value to check

Key concept

Divide and Conquer

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Divide and Conquer

In the context of Divide and Conquer algorithmic problems in GATE CS, questions test the ability to compute optimal contiguous subarray properties on concrete numerical sequences. While standard divide and conquer formulations solve such problems recursively in O(n n), students are tested on accurately finding the final numerical value (such as the maximum contiguous subarray sum), which can also be validated linearly.

Full Divide and Conquer guide →

More from GATE CSE 2019

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Algorithms · Divide and Conquer

Official IIT answer key · IIT Madras · Audited Aug 2026

Take topic test

GATE CSE 2019 Q25 · NAT · 1 mark

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: _______.

Numerical answer

Enter a value to check

Key concept

Divide and Conquer

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Divide and Conquer

Full Divide and Conquer guide →

More from GATE CSE 2019

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

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: _______.

Step-by-step verified solution

Check you can still solve Divide and Conquer under a clock

More from GATE CSE 2019

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: _______.

Step-by-step verified solution

Check you can still solve Divide and Conquer under a clock

More from GATE CSE 2019

Step-by-step verified solution

Check you can still solve Divide and Conquer under a clock

More from GATE CSE 2019

Share this solution

Step-by-step verified solution

Check you can still solve Divide and Conquer under a clock

More from GATE CSE 2019

Share this solution