动态规划求解最大字段和及其变种问题

作者：lihao21

版权所有，转载请标明出处。

动态规划（DP）为一常用算法思想，本文讲述如何利用DP解决常见的最大字段和及其变种问题。

一、 最大字段和问题

问题定义

设数组为a[k]，1≤k≤n，最大字段和X定义为：

X直观含义即，求任一连续字数组的最大和。

问题分析

不妨设：

b[j]的直观含义为，以a[j]为结束元素的连续数组的最大和。

由X和b[j]的定义，易知：

这也可以理解。设想一下，所求得的连续字数组肯定以某个元素结束，求出所有的“以某个元素结束的连续数组最大和b[j]”，取其最大的b[j]，即为X。

下面求b[j]。

（1） 当b[j-1] > 0时，无论a[j]为何值，b[j] = b[j-1] + a[j]；

（2）当b[j-1]≤0时，无论a[j]为何值，b[j] = a[j];

例子

k	1	2	3	4
a[k]	3	-4	2	10
b[k]	3	-1	2	12

其中，b[1] = a[1]，b[2] = b[1] + a[2]，b[3] = a[3]，b[4] = b[3] + a[4]；因此，对数组a，最大字段和为b[4]，即X = 12。

代码

int b[n + 1];
b[1] = a[1];
int X= a[1];
for(int i = 2; i <= n; i++) {
	if(b[i - 1] <= 0) {
		b[i] = a[i];
	} else {
		b[i] = a[i] + b[i - 1];
	}

	if(b[i] > X)
		X = b[i];
} // end of “for”

算法时间复杂度为O(n)。

二、最大字段和问题的变种

1．两个不重叠（可相邻）连续字数组的最大和。

问题定义

设数组a[t]，1≤t≤n，两个不重叠连续字数组的最大和定义为：

问题分析

应用了求最大字段和的方法。其求解算法如下：

（1）从头到尾扫描一遍数组，其循环下标i从1增加到n，依次求得字数组a[1…i]的最大字段和，将结果保存在maxSum[1…n]数组；

（2）从尾到头扫描一遍数组，其循环下标i从n减小到1，依次求得字数组a[i…n]的最大字段和，将结果保存在rMaxSum[1…n]数组；

（3）从尾到头扫描一遍数组（其实哪个方向无所谓），其循环下标从n-1到1，求和maxSum[i] + rMaxSum[i+1]，取最大的结果，即max{ maxSum[i] + rMaxSum[i+1]}，1≤i≤n-1，即为所要求的结果。

例子

t	1	2	3	4
a[t]	3	-4	2	10
b[t]	3	-1	2	12
maxSum[t]	3	3	3	12
rb[t]	11	8	12	10
rMaxSum[t]	12	12	12	10

其中，rb数组与b数组的作用类似，只不过rb[j]保存的是“从尾到头方向，以a[j]元素为结束元素的连续数组的和的最大值”。而rMaxSum同样只需根据rb数组即可求出。

代码

以POJ上面2593题“Max Sequence”为例给出相应的代码。

#include <stdio.h>

const int MAX = 100005;
int arr[MAX];
int maxSeqHere[MAX], rMaxSeqHere[MAX]; //保存字数组的最大字段和，分正向和反向。
int maxEndingHere[MAX], rMaxEndingHere[MAX]; //保存“以某个元素为结束元素
                                        //的字数组”的最大和，同样分正向和反向。

int main()
{
    int n;
    while(scanf("%d", &n), n != 0) {
        /*初始化*/
        for(int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }

        /*以下从头到尾扫描数组，求得字数组的最大字段和*/
        maxEndingHere[0] = arr[0];
        maxSeqHere[0] = arr[0];
        int maxTemp = arr[0];
        for(int i = 1; i < n - 1; i++) {
            /*利用“问题分析“中b[j]的求法*/
            if(maxEndingHere[i - 1] < 0) {
                maxEndingHere[i] = arr[i];
            } else {
                maxEndingHere[i] = arr[i] + maxEndingHere[i - 1];
            }

            if(maxEndingHere[i] > maxTemp)
                maxTemp = maxEndingHere[i];

            maxSeqHere[i] = maxTemp;
        }

        /*以下从尾到头扫描数组，求得字数组的最大字段和*/
        rMaxEndingHere[n - 1] = arr[n - 1];
        rMaxSeqHere[n - 1] = arr[n - 1];
        int rMaxTemp = arr[n - 1];

        int maxSumOutput = rMaxSeqHere[n - 1] + maxSeqHere[n - 1 - 1]; //保存输出结果

        for(int i = n - 2; i > 0; i--) {
            if(rMaxEndingHere[i + 1] < 0) {
                rMaxEndingHere[i] = arr[i];
            } else {
                rMaxEndingHere[i] = arr[i] + rMaxEndingHere[i + 1];
            }

            if(rMaxEndingHere[i] > rMaxTemp)
                rMaxTemp = rMaxEndingHere[i];

            rMaxSeqHere[i] = rMaxTemp;
            /*直接在反向扫描中求maxSumOutput即可，不用再多一次扫描*/
            if(rMaxSeqHere[i] + maxSeqHere[i - 1] > maxSumOutput)
                maxSumOutput = rMaxSeqHere[i] + maxSeqHere[i - 1];
        }

        printf("%d\n", maxSumOutput);
    }

    return 0;
}