题解 | #最大序列和#
最大序列和
http://www.nowcoder.com/practice/df219d60a7af4171a981ef56bd597f7b
“连续序列”，直接线性dp即可
因为只能是连续序列，最值无法传递到末尾
所以使用一个maxSum来记录最值
所以使用一个maxSum来记录最值
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int N;
int seq[1000000];
long long dp[1000000];
while(cin>>N){
if(N==0) break;
cin>>seq[0];
dp[0] = seq[0];
int maxSum = dp[0];
for(int i=1;i<N;i++){
cin>>seq[i];
dp[i] = max((long long)seq[i],dp[i-1]+seq[i]);
if(dp[i]>maxSum) maxSum = dp[i];
}
cout<<maxSum<<endl;
}
return 0;
}
查看5道真题和解析