一个简单的动态规划有关问题

一个简单的动态规划问题

题目来源于POJ，是一道非常基础的动态规划题目。但是却耗费了我非常多的时间，时间复杂度也从N的三次方，降到N的平方，最后优化到0(n)才最终得以通过。

题目如下：

一个简单的动态规划有关问题

要求其实非常简单，已知给你a1,a2....an，总共n个数，要求你从中抽取出两个连续的子序列，当然，如题意所示，两个序列连续在一起也是OK的，然后将其中最大的序列和输出即可。

看到题目，第一想法非常简单，从n个数中选择一个数k，将A分为1~k和k+1~n两部分。然后求出两部分内各自的最大子序和，合并起来的到Dk，然后从n中情况中选出最大的Dk就是所要求的结果d(A)了。那么每个1~k或是k+1~n中的最大子序列怎么求呢？因为之前刚看过LCS的解法嘛，很简单，构造一个Ci,j。表示ai~aj的序列和。当i=j时，Ci,j就是ai。然后逐步求出j-i的值从1到n-1的所有情况。例如，当j-i更新时，新的Ci,j=ai,i+Ci+1,j。然后再用两个数组bMAX[k],表示以k作为分割，前面k个元素中的最大子序和。同理aMAX[k]为后n-k个元素的最大子序和。并且没有必要保留每个Cij，当j-i加一的时候，将原有的Cij更新，并且更新相应的aMAX[i]和bMAX[i]就可以了。下面是源代码展示：

        for(int i=1;i<=n;i++){
            scanf("%d",&c[0][i]);
            c[1][i]=c[0][i];
        }
        bMax[2]=c[0][1];
        for(int i=3;i<=n-1;i++)
            bMax[i]=bMax[i-1]>c[0][i-1]?bMax[i-1]:c[0][i-1];
        aMax[n-1]=c[0][n];
        for(int i=n-2;i>=2;i--)
            aMax[i]=aMax[i+1]>c[0][i+1]?aMax[i+1]:c[0][i+1];

        for(int gap=1;gap<n;gap++){
            for(int i=1;i<=n-gap;i++){
                c[1][i]=c[0][i]+c[1][i+1];
                bMax[i+gap+1]=bMax[i+gap+1]>bMax[i+gap]?bMax[i+gap+1]:bMax[i+gap];
                bMax[i+gap+1]=bMax[i+gap+1]>c[1][i]?bMax[i+gap+1]:c[1][i];
            }
        }

        for(int gap=1;gap<n;gap++){
            for(int i=n;i>=1+gap;i--){
                c[1][i]=c[0][i]+c[1][i-1];
                aMax[i-gap-1]=aMax[i-gap-1]>aMax[i-gap]?aMax[i-gap-1]:aMax[i-gap];
                aMax[i-gap-1]=aMax[i-gap-1]>c[1][i]?aMax[i-gap-1]:c[1][i];
            }
        }

        int ans=aMax[2]+bMax[2];

        for(int i=3;i<n;i++)
            ans=ans>aMax[i]+bMax[i]?ans:aMax[i]+bMax[i];

其实在上面的代码中时间复杂度为n的平方，因为在例如更新aMAX的时候，是从aMAX[i-gap-1]的当前值,以及aMAX[i-gap]和新获得的c[1][i]中选择。而原先的策略是，每次新获得一个c[1][i]就更新它之前的全部aMAX。因此这样时间复杂度就是n的三次方了。

不过，上述做法的效率还是太低了。最好的做法时间复杂度完全能在0(n)解决。其实我们可以用动态规划的思维仔细想一下。如果用L[i]表示ai（不包括ai）之前的最大子序列的和。那么L[i]的值只能来源于两种情况。第一L[i]=L[i-1]即前i-1个数的最大子序列不包含新加入的ai-1。还有一种情况就是L[i]=ai-1+prefix。prefix指的是ai-1之前ai-2,ai-3...能达到的最大子序和。当然，在最初的时候prefix是为0的，然后例如在取得L[i]的值后，将prefix更新为prefix+ai-1。当prefix为正的时候，毫无疑问要加上它。但如果它为负数呢？那我们就把它更新为0，也就是不加前缀了。由此通过一次遍历，便能求出所有的L[i]。然后，同理经过一次相同的反向遍历求得R[i](此时包括ai)获得ai之后所有元素的最大子序和。最后再从L[i]+R[i]中取出最小值即可。

具体的代码如下：

        L[1]=-10000-1;
        prefix=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&A[i]);

            L[i+1]=L[i]>prefix+A[i]?L[i]:prefix+A[i];
            if(prefix+A[i]>=0)
                prefix=prefix+A[i];
            else
                prefix=0;
        }

        R[n]=A[n];
        prefix=0;
        for(int i=n-1;i>=1;i--){
            R[i]=R[i+1]>prefix+A[i]?R[i+1]:prefix+A[i];

            if(prefix+A[i]>=0)
                prefix=prefix+A[i];
            else
                prefix=0;
        }

        int ans=L[2]+R[2];
        for(int i=3;i<=n;i++)
            ans=ans>L[i]+R[i]?ans:L[i]+R[i];

一个简单的动态规划有关问题

相关推荐