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

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

int main() {
    int n;
    while(cin>>n){
        if(n==0)return 0;
        int arr[n];
        //读取数组
        for(int i =0;i<n;i++)
            cin>>arr[i];
        //构造dp
        int dp[n];
        for(int i =0;i<n;i++)
            dp[i]=INT_MIN;
        int left=arr[0],right=arr[0];
        dp[0] = arr[0];
        int maybe = arr[0];
        for(int i=1;i<n;i++){
            dp[i] = max(arr[i],arr[i]+dp[i-1]);
            //可能需要移动left
            if(arr[i]>arr[i]+dp[i-1]){
                maybe = arr[i];
                // cout<<"mark"<<i<<endl;
            }
            if(dp[i] >*max_element(dp,dp+i) && ((dp[i] >*max_element(dp+i+1,dp+n))||(i == n-1))){
                left = maybe;
            }
        }
        int maxNum=dp[0];
        int rightNum = 0;
        for(int i =1;i<n;i++){
            if(dp[i]>maxNum){
                maxNum = dp[i];
                right = arr[i];
                rightNum=i;
            }
        }
        //补充（评论区left的找法：dp数组中从righ往左数，第一个为负的位置+1即为left
        left = arr[0];
        for(int i =rightNum;i>=0;i--){
            if(dp[i]<0){
                left = arr[i+1];
                break;
            }
        }
        if(maxNum<0){
            cout<<0<<" "<<arr[0]<<" "<<arr[n-1]<<endl;
        }else{
            cout<<maxNum<<" "<<left<<" "<<right<<endl;
        }
            
        
    }
}
// 64 位输出请用 printf("%lld")

//评论区方法：从right往左数第一个dp为负的位置+1即为left