连续最大子列和的动态规划写法

连续最大子列和的动态规划写法
题目：
给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为{ Ni, Ni+1, …,
Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，
例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和
为20。
在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该
子序列的第一个和最后一个元素。

现在我们来分析一个这个问题

对于dp[i]来说，他所代表的含义是前i个的最大连续子列和
这个地方因为要保证这个子序列是连续的，所以我们的dp[i]不能仅仅考虑值最大，而是连续的子列和
那么对于最大连续子列和来说，往往是有两种情况，一种是一直相加，中间某一过程中最大，另一种是重新开始的子列和最大
如果dp[i-1]+a[i]>a[i] 那么dp[i]=dp[i-1]+a[i]
否则，dp[i]=a[i];
这就是此题的动态转移方程

#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{

    int k,res,i,t,flag;
    while(cin>>k&&k){
    int a[12345]={0},dp[12345]={0},st[12345]={0},last[12345]={0};
        res=-inf;
        flag=0;
        for(i=0;i<k;i++){
            cin>>a[i];
        if(a[i]>=0) flag=1;
        }

    dp[0]=a[0];
    st[0]=last[0]=0;
    res=max(dp[0],res);
    for(i=1;i<k;i++){
        if((dp[i-1]+a[i])>a[i]){
            dp[i]=dp[i-1]+a[i];
            st[i]=st[i-1];
            last[i]=i;
        }else {
            dp[i]=a[i];
            st[i]=last[i]=i;
        }
    }
    for(i=1;i<k;i++){
        if(res<dp[i]){
            t=i;
            res=dp[i];
        }
    }
    if(flag==1)
    cout<<res<<" "<<a[st[t]]<<" "<<a[last[t]]<<endl;
    else
    cout<<0<<" "<<a[0]<<" "<<a[k-1]<<endl;
    }
    return 0;
}