P1115 最大子段和

最大子段和

给出一个长度为 n n n 的序列 a a a，选出其中连续且非空的一段使得这段和最大。

第一行是一个整数，表示序列的长度 n n n。

第二行有 n n n 个整数，第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai​。

输出一行一个整数表示答案。

7
2 -4 3 -1 2 -4 3

4

选取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , − 1 , 2 } {3, -1, 2} {3,−1,2}，其和为 4 4 4。

• 对于 40 % 40% 40% 的数据，保证 n ≤ 2 × 1 0 3 n leq 2 times 10^3 n≤2×103。
• 对于 100 % 100% 100% 的数据，保证 1 ≤ n ≤ 2 × 1 0 5 1 leq n leq 2 times 10^5 1≤n≤2×105， − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 leq a_i leq 10^4 −104≤ai​≤104。

解释：
这题是典型的线性dp问题，既然是dp问题就要找出它的问题和子问题，最后写出转移状态方程
这题有点像最长不下降子序列，如果有不懂最长不下降子序列的可以看我写的另一个题解
大朋友的数字 这个是由最长不下降子序列改编的所有看这个也是一样的
所有这题的策略:

• dp[i] 前i个最大的子段但必须包括第i个，
• 转移状态方程就是dp[i] = max(dp[i-1] + a[i], a[i]])
• 因为可能会出现负数所以加上一个数之后可能还会变小， 所以还要和自己自己比较
• 2 -4 3 -1 2 -4 3
• 2 加上-4就是-2， 比-4大所以就选择-2所以目前就是（2，-2）-2是前两个的和了，然后加上3就是-1，没有3自己大， 这个就是加上了一个负数反而变小了， 所以还要和自己比，所以现在变成（2，-2， 3）了，目前3是最大的，虽然只有一个，但也是子段。
• 以此类推最后结果是（2， -2， 3， 2， 4， 0， 3）之后就遍历这个数组就ok了
• 这题最主要就是必须要包括自己， 前i个子段最大的和包括i

下面附上我的代码：

#include
using namespace std;
const int N = 2e5+10;
int dp[N], a[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i <= n; i ++)
        dp[i] = max(dp[i-1]+a[i], a[i]);
        // 转移状态方程， 
        
    int ans = -N;
    for (int i = 1; i <= n; i ++)
        ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}

（防抄袭 ）來