• 朴素O(N^2) 方法，果不其然超时

#include<iostream>
#include<vector>
const int N=1e4+10;
using namespace std;
int  list[N];
int main()
{
    int k;
    cin>>k;

    for(int i=0;i<k;i++)
    {
        cin>>list[i];
    }

    int l=0,r=0,sum=0,max=0;
    for(int i=0;i<k;i++)
       for(int j=i;j<k;j++)
       {
           sum=0;
           for(int k=i;k<=j;k++) sum+=list[k];
           if(sum>max||(sum==0&&max==0))
           {
               max=sum;
               l=i,r=j;
           }
       }
    if(max==0&&l==0&&r==0) cout<<'0'<<' '<<list[0]<<' '<<list[k-1];
    else cout<<max<<' '<<list[l]<<' '<<list[r]<<endl;
    return 0;
}

• 稍微优化下，仍然是O(N^2),但是可以pass

#include<iostream>
#include<vector>
const int N=1e4+10;
using namespace std;
int  list[N];
int main()
{
    int k;
    cin>>k;
    for(int i=0;i<k;i++)
    {
        cin>>list[i];
    }
    int l=0,r=0,sum=0,max=0;
    for(int i=0;i<k;i++)
    {
       sum=0;
       for(int j=i;j<k;j++)
       {
       sum+=list[j];
       if(sum>max||(max==0&&sum==0)) 
       {
           max=sum;
           l=i,r=j;
       }
       }
    }
    if(max==0&&l==0&&r==0) cout<<'0'<<' '<<list[0]<<' '<<list[k-1];
    else cout<<max<<' '<<list[l]<<' '<<list[r]<<endl;
    return 0;
}

• 最后是动态归划

#include<iostream>
#include<vector>
const int N=1e4+10;
using namespace std;
int  list[N];
int main()
{
    int k;
    cin>>k;

    for(int i=0;i<k;i++)
    {
        cin>>list[i];
    }

   int l=0,r=0,max=0;//记录最大子序列
   int i=0,j=0,sum=list[0];
   while(j<k)
   {
       if(sum>max||(sum==0&&max==0))
       {
           max=sum;
           l=i;
           r=j;
       }
       if(sum>0&&sum<max)
       {

       }
       if(sum<0)
       {
           i=j+1;
           sum=0;
       }
       j++;
       sum+=list[j];
   }
   if(l==0&&r==0&&max==0) cout<<'0'<<' '<<list[0]<<' '<<list[k-1]<<endl;
   else cout<<max<<' '<<list[l]<<' '<<list[r]<<endl;
    return 0;
}