数组中连续len个数字的最大和，动态规划法

问题描述，对于一个数组，挑选出连续len个数字，使其和为最大。

比如{-2,11，-4,13,-5，-2}，len=3时，解为{11，-4,13}，和为20.

很容易想到蛮力法求解，

int maxSubSum_len(constvector<int>&nums,constint&len) {

   if(len< 1)returnINT_MIN;

   intret(INT_MIN);

   intsizeOfNums = (int)nums.size();

   for(inti(0); i <= sizeOfNums - len; ++i) {

       intcurSum(0);

       for(intj(i); j <= i + len - 1; ++j) curSum +=nums[j];

       if(curSum > ret)ret = curSum;

   }//fori

   returnret;

}//maxSubSum_len

外层循环i从0到sizeOfNums-len,内存循环j完成curSum的累加，复杂度为n*len。

很容易想到这里curSum的累加，有一部分工作量是重复的，而动态规划是一种典型的“以空间换时间”的算法。

对于该问题，我们可以先预存累加结果，省去重复工作。

int maxSubSum_len(constvector<int>&nums,constint&len) {

   if(len< 1)returnINT_MIN;

   intsizeOfNums = (int)nums.size();

   vector<int>sum(sizeOfNums + 1, 0);//注意多开辟一个空间

   for(inti(1); i <= sizeOfNums; ++i) sum[i]= sum[i - 1]+nums[i - 1];//预存累加结果，sum[i]为前i个数字的累加和（nums[0]到nums[i-1]）

   intret(INT_MIN);

   for(inti(len); i <= sizeOfNums; ++i)if(sum[i]- sum[i -len]> ret)ret = sum[i]- sum[i -len];//sum[i]-sum[i-len]为nums[i-len]到nums[i-1]的和，也就是连续len个数的和

   returnret;

}//maxSubSum_len