4.1-1

What does FIND-MAXIMUM-SUBARRAY return when all elements of A are negative?

Sol’n

If \(i\) is the index of the most positive number, it will return

\[ (i, i, A[i]). \]

To show this is true, note it is easily shown to be true for a single element set. It is not hard to reason that the algorithm will continue to select the single most positive element from the respective subarray.