算法题（200）：最大子段和（动态规划）

审题：

 本题需要我们找到给定数组中的连续子段和最大的值

思路：
方法一：动态规划

根据经验，一般来说填表顺序都是从左到右，所以我们确定状态表示可以先以某个地方为结尾开始分析

（1）状态表示：f[i]表示以第i个元素为结尾的所有子段的最大子段和

（2）状态转移方程：

我们先将所有子段表示出来然后分析

所有子段列出来后，总共可以分为两类

第一类：只有自身的

那么它的子段和就是a[i]

第二类：和前面的元素组合起来的子段

他们可以看成前面的子段+自身，而前面的子段都是以i-1为结尾的子段，f[i-1]就是前面的子段和的最大值。所以第二类的子段中子段和的最大值一定是f[i-1]+a[i]

综上：状态转移方程为max(f[i-1]+a[i],a[i])

（3）初始化

由于我们的f[i]依赖与前一个f，所以我们为了正确填写f[1]，需要初始化f[0]=0

（4）填表顺序

根据状态转移方程可知是从左到右

（5）答案输出

由于最后需要的是所有子段中的最大子段和，所以我们需要遍历f数组，维护一个最大值并输出，ret初始化为f[1]即可

解题：
 

#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int f[N],a[N];//f[i]表示以第i个元素为结尾的最大子段和
int n;
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}//填表for (int i = 1; i <= n; i++){f[i] = max(f[i - 1] + a[i], a[i]);}//维护ret并输出int ret = f[1];for (int i = 1; i <= n; i++){ret = max(ret, f[i]);}cout << ret << endl;return 0;
}

P1115 最大子段和 - 洛谷