分治法解最大子序列和

上一篇文章告诉你分治法及它的简单使用

最大子序列和

问题描述

给定一个有 n (n≥1) 个整数的序列,要求求出其中最大连续子序列的和。
例如:

• 序列 (-2，11，-4， 13，-5，-2) 的最大子序列和为 20
• 序列 (-6，2,4,-7,5,3,2，-1,6，-9,10，-2) 的最大子序列和为16。

规定一个序列最大连续子序列和至少是0 (长度为0的子序列)，如果小于0，其结果为0。

分治策略

若 n>1，采用分治法求解最大连续子序列时，取其中间位置 mid=(n-
1)/2， 该子序列只可能出现3个地方。

• 该子序列完全落在左半部即 a[0, …, mid] 中。采用递归求出其最大
  连续子序列和 leftMaxSum.
• 该子序列完全落在右半部即 a[mid + 1, …, n - 1] 中。采用递归求出其最大连续子序列和 rightMaxSum.
• 该子序列跨越序列a的中部而占据左右两部分。

算法实现

#include <iostream>
using namespace std;

int max3(int a, int b, int c);
int maxsubSum(int a[], int low, int high);

int main(){
    int a[] = {11,-4,13, -5,-2};
    cout << maxsubSum(a, 0, 4);
    return 0;
}

int max3(int a, int b, int c){
    return a > b ? (a > c ? a : c) : (b > c ? b : c);
}

int maxsubSum(int a[], int low, int high){
    if(low == high)
        if(a[low] > 0)
            return a[low];
        else
            return 0;

    // 递归求解
    int mid = (low + high) / 2;
    int leftMaxSum = maxsubSum(a, low, mid);   //左部最大和
    int rightMaxSum = maxsubSum(a, mid + 1, high);   //右部最大和

     // 从中间开始，向两边分别计算最大和并相加得出 low 和 high 之间的最大和
    int leftMarginMaxSum = 0;
    int rightMarginMaxSum = 0;
    int leftMarginSum = 0;
    int rightMarginSum = 0;
    for(int i = mid; i >= low; i--){
        leftMarginSum += a[i];
        if(leftMarginMaxSum < leftMarginSum)
            leftMarginMaxSum = leftMarginSum;
    }
    for(int i = mid + 1; i <= high; i++){
        rightMarginSum += a[i];
        if(rightMarginMaxSum < rightMarginSum)
            rightMarginMaxSum = rightMarginSum;
    }
    int marginMaxSum = leftMarginSum + rightMarginSum;

    return max3(leftMaxSum, rightMaxSum, marginMaxSum);
}