题解 | #连续子数组最大和#
连续子数组最大和
https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95
#include <iostream>
using namespace std;
const int N = 200010;
int dp[N]; //dp[i] 表示数组 1~i满足的最大值
int a[N];
int main() {
int n;
scanf("%d",&n);
for(int i = 1;i<=n;i++)
scanf("%d", &a[i]);
//连续的子序列， 连续。。。
int res = -1e9;
dp[1] = a[1];
res = dp[1];
for(int i = 2;i<=n;i++){
//只要前面 i前面的最大值》0，dp[i]肯定要加上前面的
if(dp[i-1]>0){
dp[i] = dp[i-1]+a[i];
}else{ // 没有加的必要了，就从这次从新开始
dp[i] = a[i];
}
if(dp[i]>res)
res = dp[i];
}
printf("%d", res);
return 0;
}
// 64 位输出请用 printf("%lld")
#每日一题#
查看6道真题和解析