Consider the sequence A = [-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0] of 14 elements. Determine the maxi

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2019 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2019 question covers Divide and Conquer topic.

Q: What is the difficulty level of this question?

This GATE-CS 2019 Algorithm question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Consider the sequence A = [-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0] of 14 elements. Determine the maximum of S(i,j) = sum of A[k] for k from i to j, where 0 ≤ i ≤ j

Accepted Answer

Answer: 29Concept: Maximum Subarray SumUsing Kadane's algorithm (or divide and conquer): scan the array tracking current subarray sum and maximum seen so far.Tracking: Start at index 0. The key observation is that negative prefix elements (-5,-10) hurt the sum. Starting fresh at index 2: 6+3-1-2+13+4-9-1+4+12 = 29. Checking: 6+3=9, 9-1=8, 8-2=6, 6+13=19, 19+4=23, 23-9=14, 14-1=13, 13+4=17, 17+12=29, 29-3=26, 26+0=26. Maximum subarray sum = 29, achieved at i=2, j=11 (A[2] through A[11] = {6,3,-1,-2,13,4,-9,-1,4,12}).Definition: Kadane's algorithm: Initialize max_so_far = A[0], max_ending_here = A[0]. For each element x, max_ending_here = max(x, max_ending_here + x), max_so_far = max(max_so_far, max_ending_here).

Consider the sequence A = [-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0] of 14 elements. Determine the maximum of S(i,j) = sum of A[k] for k from i to j, where 0 ≤ i ≤ j

Master GATE-CS with Our Test Series

More Questions from Divide and Conquer

Frequently Asked Questions

Consider the sequence A = [-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0] of 14 elements. Determine the maximum of S(i,j) = sum of A[k] for k from i to j, where 0 ≤ i ≤ j

Master GATE-CS with Our Test Series

More Questions from Divide and Conquer

Frequently Asked Questions