简单DP。

注意：If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=10000;int n,a[maxn],sum,ans1,ans2;int dp[maxn];int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); dp[1]=a[1]; for(int i=2; i<=n; i++) dp[i]=max(dp[i-1]+a[i],a[i]); int Max=-999999999; for(int i=1; i<=n; i++) Max=max(Max,dp[i]); if(Max<0) printf("0 %d %d\n",a[1],a[n]); else { for(int i=1; i<=n; i++) { if(dp[i]==Max) { ans2=a[i]; int sum=0; for(int j=i; j>=0; j--) { sum=sum+a[j]; if(sum==Max) { ans1=a[j]; break; } } break; } } printf("%d %d %d\n",Max,ans1,ans2); } return 0;}