此题因该使用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;
}
时间复杂度: