题目链接

简洁版

#include<cstdio>
using namespace std;
int main()
{
    int k,csum=0,sum=-1,x=0,t=0,y=-1;//t 表示 成为下一个最大子序列的第一个节点
    int s[10001];
    scanf("%d",&k);
    for(int i=0;i<k;i++)scanf("%d",s+i);
    for(int i=0;i<k;i++){
        csum+=s[i];
        if(csum>sum){
            sum=csum;x=t;y=i;
        }
        if(csum<0){
            csum=0;t=i+1;
        }
    }
    if(y==-1)   printf("0 %d %d\n",s[0],s[k-1]);
    else printf("%d %d %d\n",sum,s[x],s[y]);
}

通俗版

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int arr[maxn];
int dp[maxn];
int pre[maxn]={0};
int main(){
    int n,m,s,e,st,ed;
    bool flag = false; 
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>arr[i];
        if(arr[i] >= 0) flag = true;
    }
    if(flag == false){
        cout<<"0 "<<arr[0]<<" "<<arr[n-1]<<endl;
        return 0;
    }
    m = dp[0] = arr[0];
    st = ed = s = e = 0; 
    for(int i = 1; i < n; i++){
        if(dp[i-1] + arr[i] >= arr[i]){ //等号很关键 0 5 dp[0]=0 dp[1] = 5 索引应该为0+1 =1 而不是1+1=2 
            dp[i] = dp[i-1] + arr[i];
            pre[i] = pre[i-1];
        }else{
            dp[i] = arr[i];
            pre[i] = i;
        }
    }
    int k = 0;
    for(int i = 1;i < n;i++){
        if(dp[i] > dp[k]){
            k = i;
        }
    }
    cout<<dp[k]<<" "<<arr[pre[k]]<<" "<<arr[k]<<endl;
    return 0;
}