分治算法(Divide and Conquer)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了分治算法(Divide and Conquer)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1769字，纯文字阅读大概需要3分钟。
内容图文
分治算法
在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法所能解决的问题一般具有以下几个特征：
-
- 问题的规模缩小到一定的程度就可以容易地解决
- 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
- 利用该问题分解出的子问题的解可以合并为该问题的解
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
分治法的三个步骤是：
- 分解（Divide）：将原问题分解为若干子问题，这些子问题都是原问题规模较小的实例。
- 解决（Conquer）：递归地求解各子问题。如果子问题规模足够小，则直接求解。
- 合并（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_maxint 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;
}
原文：http://www.cnblogs.com/StartoverX/p/4575744.html
内容总结
以上是互联网集市为您收集整理的分治算法(Divide and Conquer)全部内容，希望文章能够帮你解决分治算法(Divide and Conquer)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。