【动态规划基础】求最大连续子序列和—

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

最大子段和

题目描述

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

输入格式

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

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

输出格式

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

样例

样例输入

7
2 -4 3 -1 2 -4 3

样例输出

提示

样例 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$ 。

基本方法

当解决最大连续子序列和问题时，可以使用两种基本方法：暴力法和动态规划法。

纯暴力

暴力法是最直观的解决方法，它通过遍历所有可能的子序列，并计算它们的和，最后返回最大的和。具体步骤如下：
初始化一个变量 $ma xx$ 为负无穷大，用于记录最大和。
使用两个嵌套循环遍历所有可能的子序列起点和终点。
在内层循环中，计算当前子序列的和，并将其与 $ma xx$ 进行比较，更新 $ma xx$ 。
最后返回 $ma xx$ 作为结果。
例如，对于序列 $[- 2, 1, - 3, 4, - 1, 2, 1, - 5, 4]$ ，暴力法将遍历所有可能的子序列，计算它们的和，并返回最大的和，即 $6$ ，对应子序列 $[4, - 1, 2, 1]$ 。

暴力法的时间复杂度为 $O(n^2)$ ，其中 $n$ 是序列的长度。

动态规划法

动态规划法是一种更高效的解决方法，它通过利用子问题的最优解来构建整个问题的最优解。具体步骤如下：
初始化两个变量 $ma xx$ 和 $ll$ ，分别用于记录全局最大和和当前子序列的和。
遍历整个序列，对于每个元素，将其与 $ll$ 相加，如果结果大于当前元素本身，则更新 $ll$ 为相加结果；否则，将 $ll$ 更新为当前元素。
在每次更新 $ll$ 时，将其与 $ma xx$ 进行比较，如果 $ll$ 大于 $ma xx$ ，则更新 $ma xx$ 为 $ll$ 。
最后返回 $ma xx$ 作为结果。
例如，对于序列 $[- 2, 1, - 3, 4, - 1, 2, 1, - 5, 4]$ ，动态规划法将遍历整个序列，计算当前子序列的和，并更新 $ma xx$ 和 $ll$ 。最终，返回 $ma xx$ 的值为 $6$ ，对应子序列 $[4, - 1, 2, 1]$ 。

动态规划法的时间复杂度为 $O (n)$ ，其中 $n$ 是序列的长度。

总结：暴力法是一种简单直观的解决方法，但在处理大规模序列时效率较低。动态规划法通过利用子问题的最优解，将问题分解为更小的子问题，从而提高了效率。在实际应用中，动态规划法是解决最大连续子序列和问题的常用方法。文章来源地址https://www.toymoban.com/news/detail-769881.html

A C 代码

#include <bits/stdc++.h>
using namespace std;
long long n,a,ll,maxx;
int main() {
	cin >>n >>a;
	ll=a; maxx=a;
	for (int i=2;i<=n;i++)
	{
		cin >>a;
		if (ll+a<0)
			ll=0;
		else
		{
			ll+=a;
			maxx=max(maxx,ll);
		}
	}
	cout <<maxx;
	return 0;
}