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

发布于 / 数据结构与算法 / Comments Off on 动态规划--最大连续子序列和

0x00、引言

假设有这么一道题:

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

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

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;
}

转载原创文章请注明,转载自: 斐斐のBlog » 动态规划--最大连续子序列和
评论已关闭