最大子序列和

思路用dp[i]，记录以i为末尾元素的子序列和。相对于 之前的，只要增加end去 记录最大子序列和的 最后一个元素位置就可以，end确定后，从end往前找到一个小于0的位置，然后再+1，就是子序列开始，也就是begin的位置。

#include<iostream>
#include<math.h>
using namespace std;
const int maxn=10000;
int arr[maxn];
int dp[maxn];
int K; 
void MaxSubsquence(int n){
    if(n==1){
        cout<<arr[0]<<" "<<arr[0]<<" "<<arr[0]<<endl;return ;
    }
    int sum=0,max1=arr[0],before=0,end=0;
    dp[0]=arr[0];
    if(arr[0]<0) sum++;
    for(int i=1;i<n;i++){
        dp[i]=max(arr[i],(dp[i-1]+arr[i]));
        if(arr[i]<0)sum++;
        if(max1<dp[i]){
            max1=dp[i];
            end=i; //如果有相同的最长子序列和，通过end记录下标靠前的。
        }
    } 
    if(sum==n){  //记录负数，全为负数的话输出0
        cout<<0<<" "<<arr[0]<<" "<<arr[n-1]<<endl;
    }else{
        int i=end;
        while(dp[i]>=0&&i>-1)i--; //从end往前找到第一个小于0的，然后再加一 就是序列的begin
        cout<<max1<<" "<<arr[++i]<<" "<<arr[end]<<endl;    
    }
}
int main(){
    while(cin>>K){
        if(K==0)break;
        for(int i=0;i<K;i++){
            cin>>arr[i];
        }
        MaxSubsquence(K);
    }
    return 0;
}