You are given an array of n integers. Consider the problem of finding the sum cl

Question

You are given an array of n integers. Consider the problem of finding the sum closest to 330 in any contiguous sub-vector of the input. For example, in the array [ -6, 12, -7, 0, 14, -7, 1, -3 ] the closest sum of 19 is achieved by summing the contiguous elements [12, -7, 0, 14].

Provide pseuodocode, explain in words, and analyze a linear-time dynamic programming algorithm for solving this problem.

You are given an array of n integers. Consider the problem of finding the sum closest to 330 in any contiguous sub-vector of the input. For example, in the array t-6, 12 -7, o, 14 -7, 1, -3 the closest sum of 19 is achieved by summing the contiguous elements 12 -7, 0, 14] Provide, explain, and analyze a linear-time dynamic programming algorithm for solving this problem. For partial credit, you may instead give a quadratic-time algorithm. Please explain your algorithm in words rather than just giving pseudocode.

Explanation / Answer

Please give the thumbs up, if it is helpful for you. Thank you!!

Initialize:
closest_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(closest_so_far < max_ending_here and max_ending < 330)
closest_so_far = max_ending_here
return closest_so_far

Time Complexity: O(n)
Algorithmic Paradigm: Dynamic Programming

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.