分治算法(自刷)
分治算法自刷
分治算法的核心思想分治算法的核心思想就是四个字,分而治之,也就是将原来的问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解. 看起来有点像递归,不过要知道分治算法是一种处理问题的思想,递归是一种编程技巧.看起来像是因为分治算法一般都比较适合用递归去实现
分治算法递归实现步骤1. 分解： 将原问题分解为一系列的子问题
2. 解决：递归地求解各个子问题，若子问题足够小，则直接求解。
3. 合并：将子问题的结果合并为原问题
53.最大子序和
53.最大子序和给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
123输入: [-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. 分治 ...
