分治算法的思想是将原问题递归分成若干个子问题，直到问题满足边界条件，停止递归，最后算法层层合并，得到原问题的答案。
分治算法适用情况：
1. 原问题的计算复杂度随着问题的规模的增加而增加。
2. 原问题能够被分解为更小的子问题。
3. 子问题的结构和性质与原问题一样，并且互相独立，子问题之间不包含公共的子子问题。
4. 原问题分解出的子问题的解可以合并为该问题的解。
分治算法练习1：
leetcode #50 Pow(x, n)
难度中等474
实现pow(x,n)，即计算 x 的 n 次幂函数
这道题目要求计算n个x相乘的结果。可以通过循环n次*=暴力求解，时间复杂度为O(n)。
通过分治思想可以将求解过程分解为若干个子问题，从而降低时间复杂度。
举例来说，2 ^ 8可以被分解 2 ^ 4 * 2 ^ 4，继续分解为 2 ^ 2 * 2 ^ 2，继续分解为 2 ^ 1 * 2 ^ 1，2的1次方为本身，作为边界条件直接返回。
需要注意的是如果n（初始的n或者递归过程中出现的幂次）为奇数，则分解为 x * x ^ (n//2) x ^ (n//2)
如果n为负数，则最后的边界条件为-1，返回x的倒数。
代码如下：
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 1:
return x
if n == -1:
return 1/x
if n == 0:
return 1
if n % 2 == 0:
return self.myPow(x, n//2) ** 2 if n % 2 == 0 else x * self.myPow(x, n//2) ** 2
时间复杂度为O(logn)。
分治算法练习2：
leetcode #53
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解法1：动态规划
这道题较优解法是动态规划，并且比分治法更好想一些。
如果前i个元素和为负数，那么后面的子序列和无论多大，加上前i个元素只会起到副作用。
状态转移方程：
for i in range(1, len(nums)-1)
dp[i] = nums[i] if dp[i-1] < 0 else dp[i] = max(dp[i-1]+nums[i]
初始条件，建立和nums长度相等的一个列表dp，第一个元素为nums的第一个元素。
空间复杂度优化：由于后一个dp元素只和前一个有关，所以可以把长为n的列表空间缩小为一个元素的空间
代码如下：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
i = 0
dp = nums[0]
max_val = dp
while i <= len(nums)-2:
i += 1
if dp < 0:
dp = nums[i]
else:
dp += nums[i]
max_val = max(max_val,dp)
return max_val
时间复杂度：O(n)
解法2：分治算法
将原问题递归分为左子问题和右子问题，分别输出左子区间和右子区间中的最大和连续子序列的结果，再计算跨越中线的最大和连续子序列结果，三者进行比较，输出最大值作为该层的输出值。
终止条件：当子区间长度为1时，直接返回这一个元素。
代码如下：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
return nums[0] if n == 1
#左子问题的解
left = self.maxSubArray(nums[:n//2])
#右子问题的解
right = self.maxSubArray(nums[n//2:])
max_l = nums[n//2-1]
tmp = 0
for i in range(n//2-1,-1,-1)
tmp += nums[i]
max_l = max(tmp, max_l)
max_r = nums[n//2]
tmp = 0
for i in range(n//2,n)
tmp += nums[i]
max_r = max(tmp, max_r)
return max(left, right, max_l+max_r)
时间复杂度：O(nlogn)
分治算法练习3：
leetcode #169 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
问题可以分解为左子区间的众数，和右子区间的众数在整个区数内统计各自出现的次数并进行比较，返回多的那个数。
代码如下：
class Solution:
def majorityElement(self, nums, lo=0, hi=None):
def majority_element_rec(lo, hi):
if lo == hi:
return nums[lo]
mid = (hi-lo)//2 + lo
left = majority_element_rec(lo, mid)
right = majority_element_rec(mid+1, hi)
# 终止条件：如果子区间只有一个元素，则直接返回这个元素
if left == right:
return left
# 统计左子区间返回的数和右子区间返回的数在原区间出现的次数，并比较
left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)
right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)
return left if left_count > right_count else right
return majority_element_rec(0, len(nums)-1)
时间复杂度：O(nlogn)
