4.1 最大子数组问题

使用分治策略的求解方法

alt

伪代码过程 FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)

//接受数组A和下标low,mid,high为输入
//返回一个下标元组跨越中点的最大子数组的边界
//并返回最大子数组中值的和
FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
  //求出左半部A[low..mid]的最大子数组
  left-sum = - ∞//初始化变量left-sum，保存目前为止找到的最大和
  sum = 0//初始化变量sum，保存A[i..mid]中所有值的和
  for i = mid downto low
    sum = sum + A[i]
    if sum > left-sum//找到一个子数组A[i..mid]的和大于left-sum时
      left-sum = sum//将left-sum更新为这个子数组的和
      max-left = i//更新变量max-left来记录当前下标i
  //求右半部A[mid+1..high]的最大子数组
  right-sum = - ∞
  sum = 0
  for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right-sum
      right-sum = sum
      max-right = j
  return(max-left,max-right,left-sum + right-sum)//返回下标max-left和max-right，划定最大子数组的边界，并返回子数组A[max-left..max-right]的和left-sum + right-sum

伪代码

//初始调用FIND-MAXIMUM-SUBARRAY(A,1,A.length)会求出A[1..n]的最大子数组
FIND-MAXIMUM-SUBARRAY(A,low,high)
  if high == low
    return (low,high,A[low])//base case:only one element
  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)
    else return (cross-low,cross-high,cross-sum)

4.1-5

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray A[1..j], extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray A[i..j+1], for some 1≤i≤j+1. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j.

alt

Solution

伪代码过程 ITERATIVE-FIND-MAXIMUM-SUBARRAY(A)

ITERATIVE-FIND-MAXIMUM-SUBARRAY(A)
    n = A.length
    max-sum = -∞
    sum = -∞
    for j = 1 to n
        currentHigh = j
        if sum > 0
            sum = sum + A[j]
        else
            currentLow = j
            sum = A[j]
        if sum > max-sum
            max-sum = sum
            low = currentLow
            high = currentHigh
    return (low, high, max-sum)