[数据结构与算法]最大子段和（动态规划详细解析）

最大子段和

题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例 1 解释

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

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n\le 2\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$?10^4\le a_i\le 10^4$。

题解

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

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

这个状态转移方成就是$dp[i]=max(dp[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\le a_i\le 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;
}