题解 | 最大序列和

//与最长公共子串类似,因为有连续的要求,直接将最大序列和作为中间状态会导致dp[i]和dp[i-1]的关系难以得出,故将中间状态设为包含右边缘的最大序列和,以保证连续的要求并得出dp[i]和dp[i-1]的关系(根据dp[i-1]的正负)
//总结:放苹果,上楼梯等排列组合问题 和 最长公共子序列,最长公共子串,最大序列和等最值问题 可考虑用动态规划解决,相比与直接递归,应记录了中间状态而减低了时间复杂度,是一种空间换时间的策略
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

long long s[1000001];//s元素范围-10^9~10^9
long long dp[1000002];//店铺[i]表示 前i个元素 包含右边缘的最大序列和
int main() {
    int n;
    while (scanf("%d", & n) != EOF) {
        for(int i=0;i<n;i++){
            scanf("%lld",&s[i]);
        }

        dp[1] = s[0];//前一个最大序列和只能是第1个元素
        long long curmax = dp[1];
        for (int i = 2; i <= n; i++) {
            if (dp[i - 1] <= 0) {
                dp[i] = s[i - 1];
            } else {
                dp[i] = dp[i - 1] + s[i - 1];
            }
            curmax = max(curmax, dp[i]);
        }
        printf("%lld\n", curmax);
    }
    return 0;
}