动态规划--最大连续子序列和

0x00、引言

假设有这么一道题：

给定一串序列A={-2, 11, -4, 13, -5, -2}，要求求出 i 和 j ，使得A_i+......+A_j的和最大。

这道题最直截了当的方法是暴力求解，从左端点到右端点依次遍历。但是这样时间复杂度会十分的高，这种问题就是最大连续子序列和问题。最好的解决办法是使用动态规划。

0x01、动态规划思想解决

我们可以这么想：比如从左往右进行遍历，累计数字之和。如果遍历到某个位置，左边的子序列数字之和小于0了，这个和就不需要继续参加运算了。因为小于0的数字继续加到下面就会使得后面的数字和不是最大的。

动态规划大致分为这么几部分：状态、决策、状态转移方程。我们使用一个数组dp来定义状态，根据上面的思想可以清晰的定义状态转移方程：

dp[i] = max{ A[i], dp[i-1]+A[i] }

也就是当前状态等于序列所在位置的数字与累计和最大的一个。

0x02、C语言实现

我们要求程序能实现这个功能：

第一行给出一个数字N，接着第二行给出N个数字组成的序列，程序要输出最大连续子序列和。

先定义一个存放序列的容器和存放状态的容器：

#define MAXN 10000
int A[MAXN], dp[MAXN];

接着读取全部数据：

scanf("%d", &cnt);
for(int i = 0; i < cnt; i++){
    scanf("%d", &A[i]);
}

处理边界：

dp[0] = A[0];

使用状态转移方程更新状态数组的所有值：

for(int i = 1; i < cnt; i++){
    dp[i] = max(A[i], dp[i - 1] + A[i]);
}

最后在状态数组里面找到最大值即可

int max = 0;
for(int i = 0; i < cnt; i++){
    if(dp[i] > max)
        max = dp[i];
}

此时max就是最大连续子序列和了，把它输出即可。

完整的代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 10000

int main(){
    int A[MAXN], dp[MAXN];
    int cnt;
    scanf("%d", &cnt);
    for(int i = 0; i < cnt; i++){
        scanf("%d", &A[i]);
    }
    dp[0] = A[0];
    for(int i = 1; i < cnt; i++){
        dp[i] = max(A[i], dp[i-1] + A[i]);
    }
    int max = 0;
    for(int i = 0; i < cnt; i++){
        if(dp[i] > max){
            max = dp[i];
        }
    }
    printf("%d", max);
    return 0;
}