洛谷P1115题解

题目传送门

此题因该使用DP求解。

循环一下，算从第1数字到第i个数字的答案就好了。

代码：

#include <iostream>
#include <cstring>
#include <cmath>//比较最大值用的
#include <climits>//包含int的最小值，来存储dp[i]的最大值
#define MAX 200001//因为从1开始，所以MAX也要+1
using namespace std;
int n,a[MAX],dp[MAX],ma=INT_MIN;//ma:dp[i]的最大值
int main()
{
	memset(dp,0,sizeof(dp));//初始化
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)//dp函数
	{
		dp[i]=max(a[i],dp[i-1]+a[i]);//选择之前还是现在(状态转移方程)
		if(ma<dp[i])ma=dp[i];//给变量ma刷新
	}
	printf("%d",ma);//输出答案
	return 0;
}

时间复杂度: $O(n)$