首页 > 代码库 > 动态规划求取连续数组最大和

动态规划求取连续数组最大和

int main()
{
const int size=10;
int array[size]={3,-3,-4,10,-11,2,-3,5,-7,-3};
int MaxSumOfArray[size]={0};

MaxSumOfArray[0]=array[0];
int currentSum=0;
for(int i=1;i<size;i++){
    currentSum+=array[i];

       if(currentSum>=0)
       {
       MaxSumOfArray[i]=MaxSumOfArray[i-1]+currentSum>array[i]?

MaxSumOfArray[i-1]+currentSum:array[i];        }        else        {         MaxSumOfArray[i]=MaxSumOfArray[i-1]>array[i]?MaxSumOfArray[i-1]:array[i];        }        if(MaxSumOfArray[i]!=MaxSumOfArray[i-1])        currentSum=0; } for(int i=0;i<size;i++) cout<<MaxSumOfArray[i]<<endl; return 0; } }

网上有非常多优化版本号。不能easy体现出动态规划思想。为了说明问题未採取不论什么优化。此段代码利用动态规划算法,求连续数组最大和。

代码已改动,之前有bug

此处代码,MaxSumOfArray[i]才是从0開始以i结尾子数组最大和。读者能够自行验证。

1.用还有一个等长数组保存连续数组的最大和以避免反复计算。空间换时间。避免子问题反复。

2.我们通过子问题的最优解计算出上层问题最优解。比如:

MaxSumOfArray[i]=MaxSumOfArray[i-1]+currentSum;
MaxSumOfArray[i]=MaxSumOfArray[i-1];

所以我们看,这个问题包括最优子结构和重叠子问题。因此他才适合使用动态规划思想。

文中代码。仅仅是表达思想,并没有处理非法參数等异常情况。

有些书籍,用函数f(i)表示以第i个数字结尾的子数组的最大和(可能是笔误)。那么我们须要求出max(f[0...n])。

我们能够给出例如以下递归公式求f(i)

技术分享

这里f(i)不是以第i个数字结尾的最大和。f(i)仅代表子数组和而不是最大和。


动态规划求取连续数组最大和