問題描述，對于一個數組，挑選出連續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