题解 | 最大连续子序列

//添加一个大小为2的数组记录起点和终点
//终点易确定，只要序列值增加，更新终点
//记录每次起点，序列值增加更新最大起点（序列值增加未必有新起点）
#include<iostream>
#include<cstdio>
#include<queue>
#include<climits>
using namespace std;
const int MAXN =10000;
int dp[MAXN];
int ans[2]={0,0};
int arr[MAXN];
void Function(int n){
    int answer =INT_MIN;
    int start;//每次更新的节点
    int maxstart;//重点记录每次起点得到的最大序列的起点值
    for(int i=0;i<n ; i++){
        if(i==0){
            dp[i]=arr[i];
            start=0;
        }else{
            if(arr[i]>arr[i]+dp[i-1]){
                dp[i]=arr[i];
                start=i;//新起点
            }else{
                dp[i]=dp[i-1]+arr[i];
            }
        }
        if(answer <dp[i]){
            answer=dp[i];
            maxstart =start;//得到更大值，更新最大起点
            ans[1] = arr[i];
        }
    }
    cout<<answer<<" "<<arr[maxstart]<<" "<<ans[1]<<endl;
    return;
}
int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        if(n==0){
            break;
        }
        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        Function(n);
    }
    return 0;
}