先描述“最大子段和”的概念，然后用分治法和動態規化來解決，最后添加一些功能。

對于n個元素的整數數列（可能還有負整數），求任意連續m個數（m<=n），使其和為最大。如果該子段均為負數，定義其和為0.

比如{-2 11 -4 13 -5 -2},的最大子段和為{11，-4,13}，其和為20。

該問題不能采用簡單的分治法來解決，比如上面的數組分成{-2,11，-4}和{13，-5，-2}后，一個子問題的解是11，另一個是13，然而都不可能達到最終解。

所以這個問題的兩個子問題不是相互獨立的，需要涉及子問題的交互。故采用變異的二分法來處理。

 intmaxSub_binary(constvector<int>&nums,intleft,intright){

   if(left==right)returnnums[left]> 0 ? nums[left]: 0;//處理只有一個數字的情況。

   intmid = (left + right)>> 1;//分為兩部分

   intmaxSum_left = maxSub_binary(nums,left,mid);//左邊遞歸求解

   intmaxSum_right = maxSub_binary(nums, mid +1, right);//右邊遞歸求解

    //處理腳踩兩條船的子段

   intleftSum(0);

   for(inti(mid), tmpSum(0); i >= left; --i) {

       tmpSum+= nums[i];

       if(tmpSum > leftSum)leftSum = tmpSum;

   }//fori

   intrightSum(0);

   for(inti(mid + 1), tmpSum(0); i <= right; ++i) {

       tmpSum+= nums[i];

       if(tmpSum > rightSum)rightSum = tmpSum;

   }//fori

    //比較子段和的大小，選擇返回哪一部分的子段和

   intmaxSum_twoParts = leftSum + rightSum;

   if(maxSum_twoParts < maxSum_left&&maxSum_right < maxSum_left)returnmaxSum_left;

   if(maxSum_twoParts < maxSum_right)returnmaxSum_right;

   returnmaxSum_twoParts;

}//maxSub_binary

如果分治法的子問題不能相互獨立，也就是子問題相互重疊的情況，一般采用動態規劃法來解決。

int maxSub_dp(constvector<int>&nums) {

   intret(0);

   intlen = (int)nums.size();

   vector<int>dp(len, 0);

   dp[0]=nums[0];

   for(inti(1); i < len; ++i) {

       if(dp[i - 1]> 0)dp[i]= dp[i - 1]+nums[i];

       elsedp[i]=nums[i];

       if(dp[i]> ret)ret = dp[i];

   }//fori

   returnret;

}//maxSub_dp

下面的代碼在之前函數的基礎上，進一步得到最大子段和的長度，注意長度信息的添加位置。

由于maxSub_len_binary的返回值用來返回最大子段和的值，只能將長度信息反映在一個引用參數curLen上了。

maxSub_len_dp也是類似處理。

int maxSub_len_binary(constvector<int> &nums,intleft,intright,int&curLen) {

   if(left==right) {

       curLen= 1;

       returnnums[left]> 0 ? nums[left]: 0;

   }//if

   intmid = (left + right)>> 1;

   intleftLen(0);

   intmaxSum_left = maxSub_len_binary(nums,left,mid, leftLen);

   intrightLen(0);

   intmaxSum_right = maxSub_len_binary(nums, mid +1, right, rightLen);

   intleftSum(0), leftPartLen(0);

   for(inti(mid), tmpSum(0), tmpPartLen(0); i >= left;--i) {

       tmpSum+= nums[i];

       ++tmpPartLen;

       if(tmpSum > leftSum)leftSum = tmpSum, leftPartLen = tmpPartLen;

   }//fori

   intrightSum(0), rightPartLen(0);

   for(inti(mid + 1), tmpSum(0), tmpPartLen(0); i <= right;++i) {

       tmpSum+= nums[i];

       ++tmpPartLen;

       if(tmpSum > rightSum)rightSum = tmpSum, rightPartLen = tmpPartLen;

   }//fori

   intmaxSum_twoParts = leftSum + rightSum;

   if(maxSum_twoParts < maxSum_left&&maxSum_right < maxSum_left) {

       curLen= leftLen;

       returnmaxSum_left;

   }//if

   if(maxSum_twoParts < maxSum_right) {

       curLen= rightLen;

       returnmaxSum_right;

   }//if

   curLen= leftPartLen + rightPartLen;

   returnmaxSum_twoParts;

}//maxSub_len_binary

int maxSub_len_dp(constvector<int> &nums,int&curLen) {

   intret(0);

   intlen = (int)nums.size();

   vector<int>dp(len, 0);

   dp[0] = nums[0];

   inttmpLen(1);

   for(inti(1); i < len; ++i) {

       if(dp[i - 1] > 0)dp[i] = dp[i - 1] +nums[i],++tmpLen;

       elsedp[i] =nums[i], tmpLen = 1;

       if(dp[i] > ret)ret = dp[i],curLen =tmpLen;

   }//fori

   returnret;

}//maxSub_len_dp