文章来源：
https://blog.csdn.net/weixin_45630258/article/details/126425400
欢迎各位大佬指点、三连
下面是部分文章的内容，转发的不全，需要查看全文的老铁，链接在上面。
一、分治
1、定义：分治，也就是分而治之。
它的一般步骤是：
① 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样）
② 子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解）
③ 利用子问题的解推导出原问题的解
分治策略非常适合用递归
需要注意的是：子问题之间是相互独立的
2、分治的应用
- 快速排序
- 归并排序
- Karatsuba算法（大数乘法）
3、分治时间复杂度的计算–主定理
4、最大连续子序列和
子序列：按照原序列的排序顺序，从原序列取出部分元素
连续子序列：按照原序列的排序顺序，连续地从原序列取出部分元素
举例：
原序列：–2、1、–3、4、–1、2、1、–5、4
子序列可以是：–2、1、1、4 还可以是：4、1、4 还可以是：2、1、–5、4 等等
连续子序列可以是：–2、1、–3、4、–1 还可以是：–3、4、–1 还可以是：2、1、–5、4 等等
子串、子数组、子区间必须是连续的，子序列是可以不连续的
解法：分治
对于解：只在左边或者只在右边，可以直接使用 递归
对于解：在中间，一部分在左边，一部分在右边的情况：
- 需要先 从中间mid开始统计[mid - 1, 左边某个元素] 统计出左边的最大值
- 再从中间mid开始统计[mid, 右边某个元素] 统计出右边的最大值
- 然后左边最大值+右边最大值，就是 横跨两个区域的解
如果本文对你有帮助的话记得给一乐点个赞哦，感谢！