最大子段和（动态规划详细解析）-Toy模板网

这篇具有很好参考价值的文章主要介绍了最大子段和（动态规划详细解析）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

最大子段和

题目描述

给出一个长度为 $n$ 的序列 $a$ ，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$ 。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$ 。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

提示

样例 1 解释

选取 $[3, 5]$ 子段 ${3, -1, 2\}$ ，其和为 $4$ 。

数据规模与约定

对于 $40\%$ 的数据，保证 $\leq 2 \times 10^3$ 。
对于 $100\%$ 的数据，保证 $\leq n \leq 2 \times 10^5$ ， $-10^4 \leq a_i \leq 10^4$ 。

题解

这是一道经典的动态规划，解决这个题首先要找到状态转移方程。

最大子段和，首先这个起始位置不能为负数，如果只有一个数，那么最大子段只能说负数，如果不是，且有正数存在的情况，那么起始值肯定不是负数，初始值我们让他等于第一个值。定义dp数组，记录的是当前位置子段最大和，那么这是什么意思呢，在第一个数输进来之后，第二个数输进来，我们就开始比较，如果前面dp加上当前输入这个数比当前单独这个数小的话，很明显，前面的数据我们不需要了，那么就是需要当前这个数，并且以他开始，所以我们此时的dp就是输入的数，后续的一直这样比较。

这个状态转移方成就是 $d p [i] = ma x (d p [i - 1] + a [i], a [i])$

在我们进行上述比较的同时，我们需要注意一点那就是dp[n]并不一定是最大值，下面我们看一个例子5 200 200 -888 1 1 ，如果我们直接输出dp[n]那么就是2，很明显最大值是dp[3] 是 405，所以我们再遍历时候，就需要考虑定义一个最大值max 即我下面代码里的res，初始值为-10000，因为题目里说明 $-10^4 \leq a_i \leq 10^4$ ，那么他最小也只是-1000，设置为-10000的话，第一个数进来最大值就是第一个数。

#include <bits/stdc++.h>

using namespace std;

int n,res = -100000,dp[200001]={0},a[200001];

int main()
{
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		dp[i] = max(dp[i-1]+a[i],a[i]);
		res = res>dp[i]?res:dp[i];
	}
	cout << res;
	return 0;
}