1. In the maximum subarray problem, where the input is an array of length n, give a condition under which the output of the FIND-MAXIMUM-SUBARRAY algorithm is ( i, i+1, sum ) for some index "i" and a positive value "sum".

2. Suppose that in the maximum subarray problem the input is an array such that the values A[ i ] alternate between positive and negative (say, A[ 1 ] > 0, A[ 2 ] 0, A[ 4 ]

(i) ( i, i, sum )

(ii) ( i, i+1, sum )

(iii) ( i, i+2, sum )

for some index i and positive value sum?

Argue why or why not.

FIND-MAXIMUM-SUBARRAY(A, low, high) 1 if high == low 2 Il base case: only one element return (low, high, Alow]) 3 else mid = |(low + high)/2] (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid) (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid + 1, high) (cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) if left-sum > right-sum and left-sum > cross-sum return (left-low, left-high, left-sum) elseif right-sum > left-sum and right-sum > cross-sum return (right-low, right-high, right-sum) 11 else return (cross-low, cross-high, cross-sum) FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) 1 left-sum = -2 2 sum = 0 3 for i = mid downto low sum = sum + A[i] if sum > left-sum left-sum = sum max-left = i 8 right-sum = - 9 sum = 0 10 for j = mid + 1 to high sum = sum + A[j] if sum > right-sum 13 right-sum = sum 14 max-right = j 15 return (max-left, max-right, left-sum + right-sum) 12