a) The maximum subsequence sum problem is defined as follows: If a1, a2, ..., an are...

 

Transcribed Image Text:

a) The maximum subsequence sum problem is defined as follows: If a1, a2, ..., an are in Z, find the maximum value -a, for all i, j, 1 i jn. We assume that the answer is 0 if all the ai 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, Max Sum) 0, MaxSum - 0 1 to n 1 2 3 4 5 6 7 8 Sum for i do Sum = Sum+A[i] if Sum > Max Sum then MaxSum - Sum else if Sum <0 then Sum = 0 State precisely a loop invariant for the for loop in line 2-8. Prove that your loop invariant holds and hence conclude that the algorithm works. (5) a) The maximum subsequence sum problem is defined as follows: If a1, a2, ..., an are in Z, find the maximum value -a, for all i, j, 1 i jn. We assume that the answer is 0 if all the ai 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, Max Sum) 0, MaxSum - 0 1 to n 1 2 3 4 5 6 7 8 Sum for i do Sum = Sum+A[i] if Sum > Max Sum then MaxSum - Sum else if Sum <0 then Sum = 0 State precisely a loop invariant for the for loop in line 2-8. Prove that your loop invariant holds and hence conclude that the algorithm works. (5)