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 1 j-n, we define the quality of the pair () by a function q(i, j)--i A +, 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(nlogn) time (a) Consider the algorithm from below that solves the problem Quality-QuadrATIC(A) 1 qMax= i* = 0 5 for i- 1 to n-1 for j-n downto i+1 8 qMax = s1 + s2 10 12 13 81 =81 + Ali + 1] 14 return (i*,j*) 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 1 j-n, we define the quality of the pair () by a function q(i, j)--i A +, 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(nlogn) time (a) Consider the algorithm from below that solves the problem Quality-QuadrATIC(A) 1 qMax= i* = 0 5 for i- 1 to n-1 for j-n downto i+1 8 qMax = s1 + s2 10 12 13 81 =81 + Ali + 1] 14 return (i*,j*)