Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1,…
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) = \Sigma_{k=i}^j A[k]\) . Determine the maximum of 𝑆(𝑖, 𝑗), where 0 ≤ 𝑖 ≤ 𝑗 < 14. (Divide and conquer approach may be used.)
Answer: ________.
Attempted by 72 students.
Show answer & explanation
Correct answer: 29
Answer: 29 (maximum subsequence sum)
Method: Use Kadane's algorithm to keep a running current sum and the best (maximum) sum seen so far. For each element, set current_sum = max(element, current_sum + element) and update max_sum = max(max_sum, current_sum).
Initialize with the first element: current_sum = -5, max_sum = -5.
Iterate through the array updating current_sum and max_sum. After processing all elements the final max_sum becomes 29.
Subsequence that attains this maximum:
The contiguous block from index 2 to index 11: [6, 3, -1, -2, 13, 4, -9, -1, 4, 12].
Verification:
6 + 3 - 1 - 2 + 13 + 4 - 9 - 1 + 4 + 12 = 29
Note: A divide-and-conquer approach (maximum subarray via midpoint crossing sums) yields the same result; Kadane's algorithm is a simpler linear-time method for this task.