前缀和

#include <bits/stdc++.h>
using namespace std;
int n, ans;
int a[212345];
int sum[212345];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 预处理前缀和
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    // 枚举每个位置为子段最后一个元素时的最大子段和
    int ans = a[1];
    int minPreSum = 0; // r 前面的前缀和的最小值
    for (int r = 1; r <= n; r++)
    {
        ans = max(ans, sum[r] - minPreSum);
        minPreSum = min(minPreSum, sum[r]);
    }
    cout << ans << "\n";
    return 0;
}

贪心

#include <bits/stdc++.h>
using namespace std;
int n, ans;
int a[212345];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 贪心：只要当前子段和不是负数，那么附加到下一段就不会亏
    int ans = a[1];
    int now = 0;
    for (int i = 1; i <= n; i++)
    {
        now += a[i];
        ans = max(ans, now);
        if (now < 0)
            now = 0;
    }
    cout << ans << "\n";
    return 0;
}

动态规划

#include <bits/stdc++.h>
using namespace std;
int n, ans;
int a[212345];
int f[212345]; // f[i]: 以 a[i] 结尾的最大子段和
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 贪心：只要当前子段和不是负数，那么附加到下一段就不会亏
    int ans = a[1];
    for (int i = 1; i <= n; i++)
    {
        // 用到了前面的最大子段和/单独成一段
        f[i] = max(f[i - 1] + a[i], a[i]);
        ans = max(ans, f[i]);
    }
    cout << ans << "\n";
    return 0;
}