X03蒟蒻一只，老师课上布置的动规学习任务罢了

要使字段和（也就是区间和）最大，要么右端点大，要么左端点小

使用DP算法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本文设数组下标从1开始。 dp[1]=a[1] 因为一个数，选他就最大 接下来： dp[i]： * dp[i-1]+a[i]<0:dp[i]=0 a[1~i-1]的最大子段和加上a[i]小于零，那么就白手起家（bushi） * 否则，dp[i]=dp[i-1]+a[i] 继续累加 * 统计dp表最大值，就是最大子段和 不用管为什么，模板背下来。 参考代码：

XP03A的老傻来标个点证明me做了题

想一下状态转移方程就很简单了。

#include <iostream> #include <algorithm> using namespace std; int main(){ int n; cin >> n; // 读入 // 这里假设先读入 n，再读入 n 个数 long long cur = 0, ans = -1e18; // 用 long long 防溢出 for(int i = 0; i < n; i++){ long long x; cin >> x; cur = max(x, cur + x); // 继续累加 或 重新开始 ans = max(ans, cur); // 更新全局最大值 } cout << ans << endl; return 0; }

连续最大子段和可以看做依次读取数据，你可以对数据进行以下操作： 1.将此数据加入前面子段 2.此数据单独成一段 我们只需要取以上两种情况的较大值即可 接下来我们只需要定义一个maxn用来存储最大子段和 给出代码： 时间复杂度：o(n),没有问题