洛谷题单指南-动态规划1-P1115 最大子段和

原题链接：https://www.luogu.com.cn/problem/P1115

题意解读：计算最大字段和，典型dp问题。

解题思路：

设a[]表示所有整数，f[i]表示以第i个数结束的最大字段和

当f[i-1]>=0时，f[i] = f[i-1] + a[i]

否则，f[i] = a[i]

因此，递归式为f[i] = max(a[i], f[i-1] + a[i])

注意整数可能为负，ans初始值为INT_MIN

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int n;
int a[N];
int dp[N]; //dp[i]表示以i结尾的最大子段和
int ans = INT_MIN;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        dp[i] = max(a[i], dp[i-1] + a[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}