The maximum subsequence sum problem is defined as follows: If a_1, a_2, ...., a_

Question

The maximum subsequence sum problem is defined as follows: If a_1, a_2, ...., a_n are in Z, find the maximum value sigma^j _k = i a_i, for all i, j, 1 lessthanorequalto i lessthanorequalto j lessthanorequalto n. We assume that the answer is 0 if all the a_i are negative or if the sum is empty. The following algorithm finds a solution to the problem. Here, we assume that a, s are stored in the array A. MAXIMUM-SUBSEQUENCE(A, MaxSum) Sum leftarrow 0, MaxSum leftarrow 0 for i leftarrow 1 to n do Sum = Sum + A [i] if Sum > MaxSum then MaxSum leftarrow Sum else if Sum

Explanation / Answer

The loop invariant here is that the maxsum is always>=0.

when there is no element in the array or all the elements in the array are negative then maxsum holds the value of 0 which is its initial value.

when there are elements for example [2,3,4,5,-1,-5,-6,-7] in the array, then maxsum always holds a value which is greater than 0 i.e. 2+3+4+5 = 14. when -1 comes in the next iteration sum becomes less than 14 i.e. 13.

maxsum holds the value of the maximum sum and the value of maxsum only gets replaced with variable sum when a higher value is available in sum variable.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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