最大子数组问题

最大子数组问题

A[low...high]数组的子数组A[i...j],一定会满足一下3种情况之一：
要么在左边的一半，要么在右边的一半，要么是个跨越中点的子数组。
  1. 完全位于子数组A[low..mid]中, 因此 low<= i <= j <=mid.
  2. 完全位于A[mid+1...high]中，mid< i <= j <= high
  3. 跨域了中点 low<= i <= mid < j <= high
对于第三种情况(一定会跨越中点)，由于任何跨域中点的子数组都由A[i...mid]和A[mid...j]组成。
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
leftSum = -INT_MAX
sum = 0;
for i = mid down to low
sum = sum + A[i]
if sum>leftSum
leftSum = sum
maxLeft=i
rightSum = -INT_MAX
sum = 0
for j = mid+1 to high
sum = sum + A[j]
if sum > rightSum
rightSum = sum
maxRight = j
return (maxLeft, maxRight, leftSum+rightSum)
整个算法：n*logn
FIND-MAXIMUM-SUBARRAY(A, low, high)
if low == high logn 消耗
return (low, high, A[low])
(leftLow, leftHigh, leftSum) = FIND-MAXIMUM-SUBARRAY(A,low,mid)
(rightLow, rightHigh, rightSum) = FIND-MAXIMUM-SUBARRAY(A,mid+1,high)
(crossLow, crossHigh, crossSum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) n消耗
if leftSum>=rightSum and leftSum>= crossSum
return (leftLow, leftHigh, leftSum)
else if rightSum >= leftSum and rightSum >= crossSum
return (rightLow, rightHigh, rightSum)
else
return (crossLow, crossHigh, crossSum)