(3) (8 POINTS) We know that Kadane's algorithm used to solve the Maximum-subarray prob- lem is linear, (n), but the constant multiplying n may be large, as there are a certain fixed number of operations on each of the n steps of the algorithm, when moving along the array. Suppose that the array A is sorted in increasing order, and that you als know the value of the sum SA] A2]+A[n] of all the numbers in the array. Describe an algorithm to solve the maximum-subarray problem, under these hypotheses, whose best case is e(1) and at worst needs n + o(n) operations (comparisons and sums). Here o(n) of course means some additional term that goes to zero when divided by n as n oo. Explain using plain English, no pseudocode. (Hint: locate first in the array the smallest non-negative numper Alkl and then look at the sum Alk] + Alk +1 Aln] (Why?)