题解 | #最大序列和#
最大序列和
https://www.nowcoder.com/practice/df219d60a7af4171a981ef56bd597f7b
经典的动态规划问题：
解决问题的关键在于dp[i]数组的定义
#include <iostream>
using namespace std;
#define MAXN 1000001
#define MIN -999999
int main(){
long long dp[MAXN]={MIN};//dp[i]表示包括数组中包含第i个即A[i-1]的最大序列和
long long A[MAXN]={0};
long long N=0;
long long res=MIN;
while(cin>>N){
res=MIN;
for(int i=1;i<=N;i++){
cin>>A[i];
}
for(int i=1;i<=N;i++){
dp[i]=max(A[i],A[i]+dp[i-1]);
res=max(res,dp[i]);
}
cout<<res<<endl;
}
return 0;
}
