Go Through算法导论:最大子数组问题

2016年01月18日 原创
关键词: C++ 数据结构 分治法 算法导论
摘要 本文讲述了如何使用分治法解决最大子数组问题。

在算法导论的第四章,作者以一个投资股票来获得最大收益的问题作为引子,通过把问题变换引出了最大子数组问题。最大子数组是值一个数组的和最大的非空连续子数组。如下图,子数组A[8..11]的和是43,是A的所有连续子数组中和最大的。

求解最大子数组问题可以用蛮力法,时间复杂度很明显是Θ(n2)。然而用分治法却可以把时间复杂度给降到Θ(nlogn),下面我们来讨论用分治法来解决最大子数组问题。

对于数组A[low..high]运用分治技术意味着我们要将子数组划分为两个规模尽量相等的子数组。也就是说,找到子数组的中央位置,比如mid,然后考虑求解两个子数组A[low..mid]和A[mid+1..high]。

A[low..high]的任何连续子数组A[i..j]所处的位置必然是以下三种情况之一:

  • 完全位于子数组A[low..mid]中,因此low≤i≤j≤mid。
  • 完全位于子数组A[mid+1..high]中,因此mid+1≤i≤j≤high。
  • 跨越了中点,因此low≤i≤mid<j≤high。

对于前两种情况,可以递归的进行求解。只有第三种情况需要单独的进行求解,然后在三种情况中选择和最大的子数组。

在求解第三种情况的时候需要注意,我们应该找出经过中点的最大子数组,因此可以冲mid出发分别向左和向右进行查找,最后把各自找到的子数组进行合并。

求解跨越了中点的最大子数组的伪代码如下:

FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)

 left-sum = -∞

 sum = 0

 for i = mid downto low

   sum = sum + A[i]

   if sum > left-sum

     left-sum = sum

     max-left = i

 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)

上述代码的总迭代次数为

(mid - low + 1) + (high - mid)=n

有了一个线性时间的FIND-MAX-CROSSING-SUBARRAY在手,我们就可以设计求解最大子数组问题的分治算法的伪代码了:

FIND-MAXIMUM-SUBARRAY(A,low,high)

 if high == low

 return (low,high,A[low])

 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-hign,cross-sum) = FIND-MAXIMUM-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)

初始调用FIND-MAXIMUM-SUBARRAY(A,1,A.length)会求出A[1..n]的最大子数组。

下面是该算法的c++代码

#include<iostream>
static const int inf = -9999999;
using namespace std;
/*
arr 父数组
low 数组最左边的下标
high 数组最右边的下标
mid 数组中间的下标
crossLow,crossHigh,crossSum是函数执行的结果
*/
void findMaxCrossingSubarray(int* arr, int low, int mid, int high, int& crossLow, int& crossHigh, int& crossSum) {
    int leftSum = inf;
    int sum = 0, maxLeft = 0;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > leftSum) {
            leftSum = sum;
            maxLeft = i;
        }
    }
    int rightSum = inf, maxRight=high;
    sum = 0;
    for (int i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum>rightSum) {
            rightSum = sum;
            maxRight = i;
        }
    }
    crossLow = maxLeft;
    crossHigh = maxRight;
    crossSum = leftSum + rightSum;
}
/*
arr 父数组
low 数组最左边的下标
high 数组最右边的下标
resultLow,resultHigh,sum是函数的执行结果
*/
void findMaximumSubarray(int* arr, int low, int high, int& resultLow, int& resultHigh, int& sum) {
    if (low == high){
        resultLow = low;
        resultHigh = high;
        sum = arr[low];
        return;
    }
    int mid = 0, leftLow = 0, leftHigh = 0, leftSum = 0, rightLow = 0, rightHigh = 0, rightSum = 0, crossLow = 0, crossHigh = 0, crossSum = 0;
    mid = (low + high) / 2;
    findMaximumSubarray(arr, low, mid, leftLow, leftHigh, leftSum);
    findMaximumSubarray(arr, mid + 1, high, rightLow, rightHigh, rightSum);
    findMaxCrossingSubarray(arr, low, mid, high, crossLow, crossHigh, crossSum);
    if (leftSum >= rightSum&&leftSum >= crossSum) {
        resultLow = leftLow;
        resultHigh = leftHigh;
        sum = leftSum;
    }
    else if (rightSum >= leftSum&&rightSum >= crossSum) {
        resultLow = rightLow;
        resultHigh = rightHigh;
        sum = rightSum;
    }
    else {
        resultLow = crossLow;
        resultHigh = crossHigh;
        sum = crossSum;
    }
    

}

int main() {
    int arr[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    int resultLow, resultHigh, resultSum;
    findMaximumSubarray(arr, 0, 15, resultLow, resultHigh, resultSum);
    cout << "最大子数组下标是:" << resultLow << "~" << resultHigh << ",和为:" << resultSum << endl;
    return 0;
}

执行结果: