自动搬运

查看原文

来自洛谷，原作者为

	QianianXY www.qianianxy.cn

搬运于2025-08-24 21:44:21，当前版本为作者最后更新于2019-07-28 23:04:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到题解区没什么简短的dp代码，处理过程有的地方复杂化了，于是忍不住来一发水文。

这是道线性dp（废话），所以可以边读入边输出。本题也不需要一个a数组，一个f数组，直接合成一个数组凑合着用。

a[i]表示前i个数的最大子段和。

转移方程：a[i] = max(a[i], a[i] + a[i - 1])

由于a[n]不一定是最大值，所以设变量ans随循环更新最大值。

最后注意处理全负数的情况就好了。

总而言之，一个循环丰衣足食。

#include <bits/stdc++.h>
using namespace std;
int n, a[100001], ans = -0x7fffffff;
int main()
{
	scanf("%d", &n);
	for (register int i = 1; i <= n; i++) 
	{
		scanf("%d", &a[i]);
		a[i] = max(a[i], a[i] + a[i - 1]);
		ans = max(a[i], ans);
	}
	printf("%d\n", ans);
	return 0;
}

小蒟蒻写得那么认真，就不给个赞吗QwQ 算了，写得那么烂，就不好意思求赞了（还是给一个再走吧）...