动态规划求取延续数组最大和
动态规划求取连续数组最大和
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; } }
网上有很多优化版本,不能容易体现出动态规划思想,为了说明问题未采取任何优化。此段代码利用动态规划算法,求连续数组最大和。代码已修改,之前有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)