分治

分而治之，大到诸侯分治，小到小区管理

两个阶段

划分子集
聚合治理

分治优劣

分治算法逻辑清晰，易于实现。关键在于怎么划分，其划分的方法不同，其时间复杂度会有一定差别
划分的质量不行，时间复杂度可能不被接受，另外其耗费相当的空间

分治算法案例

最大子段和

描述：给定 n 个整数（可以为负数）的序列 $(a_{1}, a_{2}, . . ., a_{n})$ ,求 $max {0, max_{1 \leq i \leq j \leq n} \sum_{k = i}^{j} a_{k}}$ 实例： $[- 2, 11, - 4, 13, - 5, - 2]$
分析：将序列划分为左右两半，递归计算左右段最大子段和，最终取三者最大值 $r e s = max {S_{l e f t}, S_{r i g h t}, S_{1} + S_{2}}$
题解代码
- max_subarray_sum.cpp
- max_subarray_sum.py