题解 | 最大序列和

#include <functional>
#include <iostream>
#include <algorithm>
using namespace std;\
const int N = 1000010;
using ll = long long; 

ll dp[N];
ll s[N];

int main() {
    int n;
    while (cin >> n) { 
	  //初始化序列数组,序列存在0~n-1位
        for(int i=0;i<n;i++){
            cin>>s[i];
        }
	  //1.dp数组的初始状态dp[0]：子序列就是第一个元素时，最大子序列和就是本身s[0]；
        dp[0]=s[0];
        for(int i=1;i<n;i++){
           dp[i]=max(s[i],dp[i-1]+s[i]);
        }
        sort(dp,dp+n); //升序排序，并输出最大的
        cout<<dp[n-1]<<endl;
    }
}
// 64 位输出请用 printf("%lld")

【问题描述】：

​ 在一个给定的序列{A1, A2, …, An}中，找出一个连续的子序列{ Ai ,…, Aj}，使得这个连续的子序列的和最大，输出这个最大的序列和。（非常适合使用DP求解该问题，时间复杂度为O(n))

【动态规划法-算法思路】：

1. 首先设置一个数组 dp[N]，令 dp[i]表示以 A[i]作为末尾的连续序列的最大和。于是，最大连续子序列和便是数组 dp 中的最大值。
2. 由于 dp[i]是以 A[i]作为末尾的连续序列的最大和，因此只有两种情况：
1. ① 最大和的连续序列只有一个元素，即 A[i]本身，也就是说 dp[i] = A[i] ；
2. ② 最大和的连续序列有多个元素，即从前面的某个 A[j]开始，一直到 A[i]结束，也就是dp[i] = A[j] +…+ A[i−1] + A[i]。如何获得 A[j] +…+ A[i−1]呢？再回头看一下 dp的定义，dp[i]表示以 A[i]作为末尾的连续序列的最大和，此时 dp[i−1]就是 A[j] +A[j+1] +…+ A[i−1]的值，因此 dp[i] = dp[i−1] + A[i] ；
3. 通过这两种情况，于是得到状态转移方程dp[i] = max{A[i], dp[i−1] + A[i]}。只需将 i 从小到大枚举并依次遍历，即可得到整个 dp 数组。