DP_Issues

最大字段和

1.动态规划方程：

2.算法过程：

    b[i]=Max(b[i-1]+a[i],0); //b[i]为a[k..i]的字段和.可以仅为一个变量.

    maxSum[i]=Max(b[i],maxSum[i-1]);

3.代码实现：

int DP_MaxSum(int *a, int n)

{

        int i, maxSum = 0, b[0]=0;

        if(a[0] > 0)

                maxSum=b[0]=a[0];

        for(i=1; i

        {

                b[i] = (b[i-1]>0)?(b[i-1]+a[i]):a[i];

                if(maxSum < b[i])

                        maxSum = b[i];

        }

        return maxSum;

}

阅读(1166) | 评论(0) | 转发(0) |

0

上一篇：ACM:Thought-Scream

下一篇：数据库索引原理理解