首先设状态：设 f(i)f(i)f(i) 为 iii 结尾的最大子段和。转移要么就是在 f(i−1)f(i-1)f(i−1) 后面继续加 aia_iai ，要么就是 aia_iai 本身。所以取最大值即可。方程：f(i)=max(f(i−1),0)+aif(i)=max(f(i-1),0)+a_if(i)=max(f(i−1),0)+ai （先前讨论的变形）。 然后把状态数组滚动掉（雾）。

#include<iostream> using namespace std; int main() { int n,ans=-1e9,sum=0,fumax=-0; cin>>n; for(int i=0;i<n;i++) { int temp; cin>>temp; sum+=temp; int fusum=-sum; if(sum+fumax>ans)ans=sum+fumax; if(fusum>fumax)fumax=fusum; }

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

方法1思路： 看到这道题，第一眼就知道是DP，因为题目中要求的子段是连续且非空的，所以我们可维护一个DP数组，对于每一个元素，实则有两种选择：将其并入上一个元素所在子段或将其作为另一个子段的首个元素 代码呈现： 方法2思路： 我们也可以运用前缀和的思路进行解题，即一个从i到j的子段的总和可以由从1到j的子段的总和减去 从1到i的子段的总和得出。对于每一个元素i，我们需要查找以他为结尾的子段中和最大的，这里就可以使用前缀和优化。因为从第一个元素至第I个元素的值是固定的（定义sum[i]为前i个元素的和），所以问题转化为：在第1至i-1个元素中找出最小的一个（被减数固定，自然是减数越小越好），而这个问题也可以用前缀和解决（定义pre[i]为前i个元素中从1到i的总和最小的）。 代码呈现