最大子段和

题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, ..., a_n$，求一个连续子段，使得该子段内所有数的和最大（空子段不算）。

输入格式

第一行，一个整数 $n$。

第二行，$n$ 个整数，表示序列 $a$。

输出格式

一行，一个整数，表示最大子段和。

数据范围

提示

用动态规划求解。设 $dp_i$ 表示以第 $i$ 个数结尾的最大子段和，则

答案就是所有 $dp_i$ 的最大值，时间复杂度 $O(n)$。参考代码：

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    long long dp = 0, ans = -1e18;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        dp = max(dp + x, x);
        ans = max(ans, dp);
    }
    cout << ans << endl;
    return 0;
}