题解 | 最大连续子序列

#include <bits/stdc++.h>
using namespace std;

const int SIZE=10000;

int dp[SIZE];

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        memset(dp,INT_MIN,sizeof(dp));
        int a[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        for(int i=0;i<n;i++){
            if(i==0)dp[i]=a[i];
            else dp[i]=max(a[i],dp[i-1]+a[i]);
        }
        int k=0,ans=dp[0];
        for(int i=0;i<n;i++){
            if(ans<dp[i]){
                ans=dp[i];
                k=i;
            }
        }
        int j=k;
        while(j>=0){
            if(dp[j]!=a[j])j--;
            else break;
        }
        if(ans<0)cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
        else cout<<ans<<" "<<a[j]<<" "<<a[k]<<endl;
    }
}

本题难度核心在找谁是开始，谁是结束，其实你分析一下这个dp数组的状态就可以知道，如果前面存在非最优解，会从该位置截断，取a[i]当前值，那么，我们就去找这个位置即可，然后就可以轻松解决，然后本题还有个要求，对小于0的特别输出，注意一下就可完美解决#大学最后一个寒假，我想……#