题解 | #最大连续子序列#

题目要求输出第一个和最后一个元素，用s[max]保存当前最大序列的起始元素，在dp转移时根据条件判断结果决定s[i]取s[i-1]或i,最后一个元素即为i。

#include <iostream>
#include <cstdio>
using namespace std;
const int Max=10000;
int a[Max];
int dp[Max];
int s[Max];//起始元素
int main() {
    int n;
    
    while (cin >> n) { // 注意 while 处理多个 case
        int res=-1;
        if(n==0){
            break;
        }
        bool flag=false;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]>=0){
                flag=true;
            }
        }
        if(!flag){
            cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
            continue;
        }
        s[0]=0;
        int index;
        for(int i=0;i<n;i++){
            if(i==0){
                dp[i]=a[i];
            }
            else{
                if(a[i]>dp[i-1]+a[i]){
                    s[i]=i;
                    dp[i]=a[i];
                }
                else{
                    s[i]=s[i-1];
                    dp[i]=dp[i-1]+a[i];
                }
               
            }         
            if(res<dp[i]){
                res=dp[i];
                index=i;
            }
        }
        cout<<res<<" "<<a[s[index]]<<" "<<a[index]<<endl;
    }
}
// 64 位输出请用 printf("%lld")