We are given an array A[1...n] of n 2 2 positive and negative integers. The goal is to find a contiguous interval of the array to exclude so as to maximize the sum of the remaining numbers. Specifically, given two indexes l-ic j n, we define the quality of the pair (h) by a function qGJ)- 1 Ak]+=, Ak] (note that the left and right remaining portions are always non-empty) The problem is to find the pair (i*,j*) that maximizes the quality q(i*, j*). Your task is to design and analyze an algorithm solving this problem, running in O(n log n) time. a) Consider the algorithm from below that solves the problem QUALITY-QUADRATIC(A) i"=0 4 s1=A[1] for i = 1 to n-1 for j-n downtoi+1 if s1+ s2 qMax qMax = s1 + s2 is 10 12 13 14 81 = s1+Ali+11 return (*,j*) Show that the algorithm is correct (using a formal loop invariant on i-loop, and an argument of what the j-loop does). Also briefly argue that the time complexity of this algorithm is (n2) We are given an array A[1...n] of n 2 2 positive and negative integers. The goal is to find a contiguous interval of the array to exclude so as to maximize the sum of the remaining numbers. Specifically, given two indexes l-ic j n, we define the quality of the pair (h) by a function qGJ)- 1 Ak]+=, Ak] (note that the left and right remaining portions are always non-empty) The problem is to find the pair (i*,j*) that maximizes the quality q(i*, j*). Your task is to design and analyze an algorithm solving this problem, running in O(n log n) time. a) Consider the algorithm from below that solves the problem QUALITY-QUADRATIC(A) i"=0 4 s1=A[1] for i = 1 to n-1 for j-n downtoi+1 if s1+ s2 qMax qMax = s1 + s2 is 10 12 13 14 81 = s1+Ali+11 return (*,j*) Show that the algorithm is correct (using a formal loop invariant on i-loop, and an argument of what the j-loop does). Also briefly argue that the time complexity of this algorithm is (n2)