学步园

好久没做题了，望我能跨过这道坎。

DP其实自己原先做了好久还是跟没入门一样……有点不得其法……到底是哪方面能力差……

好啦，说说想法。是看了题解还是不懂的……之前脑子里一直模拟程序是怎么走的，但是真不知道为什么这样，然后刚刚……换了一种方式……我也不知道这样靠谱不……反正……看着像对的？不对的话也是我证明的方面还不够吧。

设dp[i]为以a[i]结尾的最大子序列和。

证明：dp[i]为以a[i]结尾的最大子序列和

解：1.dp[i+1]是为以a[i+1]结尾的最大子序列和

2.dp[0]满足假设

易得2成立

即证1.

因为dp[i]是以a[i]结尾的最大子序列和，若dp[i+1]=max(dp[i]+a[i],a[i])，则2.成立。

得证。

(⊙v⊙)嗯。。。。不知道是不是这样。。。

所以这个dp的转移方程就是这个啦。

#include <stdio.h>
#define ll long long
#define maxn 10010
ll a[maxn];
typedef struct node
{
    ll val,l,r;
}node;
node dp[maxn];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        int i,j=0;
        
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            if(a[i]>=0) j=1;
        }
        if(!j)
        {
            printf("0 %lld %lld\n",a[0],a[n-1]);
            continue;
        }
        dp[0].val=a[0];
        dp[0].l=dp[0].r=a[0];
        for(i=1;i<n;i++)
        {
            ll tmp=dp[i-1].val+a[i];
            if(tmp>a[i])
            {
                dp[i].val=tmp;
                dp[i].r=a[i];
                dp[i].l=dp[i-1].l;
            }
            else
            {
                dp[i].val=a[i];
                dp[i].l=dp[i].r=a[i];
            }
            //printf("---%d %d %d\n",dp[i].val,dp[i].l,dp[i].r);
        }
        node sum;
        sum=dp[0];
        for(i=1;i<n;i++)
            if(dp[i].val>sum.val) sum=dp[i];

        printf("%lld %lld %lld\n",sum.val,sum.l,sum.r);
    }
    return 0;
}

************************

这里可以进行优化，两个方面，我们可以发现，每次对比只是dp[i]与dp[i-1]对比。所以不用所有的dp值都保留，只要保留pre now即可。

所以这样一来对于输入的数据也无需储存。

代码就不贴了。。。。。

原来看网络上的极简代码也不知道是怎么来的，现在自己推出来感觉真好。有的时候代码看不懂就要动手算，无厘头的代码可能是推出来的。怎么可以从一个推出来的式子上去意淫呢？？！