题解 | #最大连续子序列#
最大连续子序列
http://www.nowcoder.com/practice/afe7c043f0644f60af98a0fba61af8e7
没看清题目要求，数字全<0时输出0 0 N-1
maxEnd在每次重新开始时更新即可
maxStart不好记录，倒推即可
#include<iostream>
#include<climits>
#include<math.h>
using namespace std;
int main(){
int K;
int data[10000];
int dp[10000];
while(cin>>K){
if(K==0) break;
cin>>data[0];
dp[0] = data[0];
long long maxSum = dp[0];
int maxEnd = 0;
for(int i=1;i<K;i++){
cin>>data[i];
int continuePut = dp[i-1]+data[i];
if(continuePut>data[i]){
dp[i] = continuePut;
} else {
dp[i] = data[i];
}
if(dp[i]>maxSum){
maxSum=dp[i];
maxEnd = i;
}
}
int maxStart = maxEnd;
int counter = maxSum;
for(int i=maxEnd;i>=0;i--){
counter-=data[i];
if(counter==0){
maxStart = i;
break;
}
}
if(maxSum<0){
maxSum=0;
maxStart = 0;
maxEnd = K-1;
}
cout<<maxSum<<" "<<data[maxStart]<<" "<<data[maxEnd]<<" "<<endl;
}
return 0;
}
