分治算法

自刷

分治算法的核心思想

分治算法的核心思想就是四个字,分而治之,也就是将原来的问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解.
  看起来有点像递归,不过要知道分治算法是一种处理问题的思想,递归是一种编程技巧.看起来像是因为分治算法一般都比较适合用递归去实现

分治算法递归实现步骤

1. 分解：

​ 将原问题分解为一系列的子问题

2. 解决：

递归地求解各个子问题，若子问题足够小，则直接求解。

3. 合并：

将子问题的结果合并为原问题

53.最大子序和

53.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。`进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

1. Post not found: 力扣自刷/动态规划

2. Post not found: 力扣自刷/贪心算法

3. 分治算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int findmax(vector<int> nums, int x, int y)
{
	int v, L, R, midMaxs;
	if (y - x == 0) { 
		return  nums[x]; 
	}
	int m = ( x + y ) / 2; //分治第一步，划分成[x,m)和[m,y)两部分
	midMaxs = max(findmax(nums, x, m), findmax(nums, m + 1, y));
	v = 0; L = nums[m]; R = nums[m+1];
	for (int i = m ; i >= x; i--)
	{
		L = max(L, v += nums[i]);
	}
	v = 0;
	for (int i = m + 1 ; i <= y; i++)
	{
		R = max(R, v += nums[i]);
	} 
	return max(L + R, midMaxs);

}
int maxSubArray(vector<int>& nums) {

	int length = nums.size();
	int result = findmax(nums, 0, length-1);
	return result;
}