[算法]分治算法(Divide and Conquer) -开发者知识库

[算法]分治算法(Divide and Conquer) -开发者知识库,第1张

轉載請注明:http://www.cnblogs.com/StartoverX/p/4575744.html 

分治算法

  在計算機科學中,分治法是建基於多項分支遞歸的一種很重要的算法范式。字面上的解釋是“分而治之”,就是把一個復雜的問題分成兩個或更多的相同或相似的子問題,這些子問題互不相交,直到最后子問題可以簡單的直接求解,原問題的解即子問題的解的合並。

  分治法所能解決的問題一般具有以下幾個特征:

    • 問題的規模縮小到一定的程度就可以容易地解決
    • 問題可以分解為若干個規模較小的相同問題,即該問題具有最優子結構性質
    • 利用該問題分解出的子問題的解可以合並為該問題的解
    • 該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子問題

  分治法的三個步驟是:

    1. 分解(Divide):將原問題分解為若干子問題,這些子問題都是原問題規模較小的實例。
    2. 解決(Conquer):遞歸地求解各子問題。如果子問題規模足夠小,則直接求解。
    3. 合並(Combine):將所有子問題的解合並為原問題的解。

  以leetcode中Maximum Subarray為例:

    Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] has the largest sum = 6。

    思路:利用分治法,最大連續子序列要么在數組的左半邊,要么在數組的右半邊,要么經過數組的中點。

    

int maxSubArray(vector<int>& nums) { if(nums.size() == 1)//遞歸退出
 { return nums[0]; } auto mid =nums.begin()   (nums.end() - nums.begin())/2; vector<int> left_vec(nums.begin(),mid); int left = maxSubArray(left_vec);//要么在數組的左邊
 vector<int> right_vec(mid,nums.end());//要么在數組的右邊
    int right = maxSubArray(right_vec); //以下計算通過數組中間的情況,分別計算left_max和right_max,相加得到mid_max
    int left_max = -1000000; int left_add = 0; for(auto iter = mid-1;iter != nums.begin();iter--) { left_add  = *iter; if(left_add > left_max) { left_max = left_add; } } left_add  = *nums.begin(); if(left_add > left_max) { left_max = left_add; } int right_max = -1000000; int right_add = 0; for(auto iter = mid;iter != nums.end();iter  ) { right_add  = *iter; if(right_add > right_max) { right_max = right_add; } } right_max = right_max >= right_add ? right_max : right_add; int mid_max = right_max   left_max; //right,left,mid_max三個比大小,大的為答案
    int rl_max = (right > left? right:left); return mid_max > rl_max ? mid_max : rl_max; }

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复