分治法思想：
递归计算前半部分的最大子列和，递归计算后半部分的最大子列和，然后计算跨前后两个区域的最大子列和，这三个子列和进行比较即可。
前后的计算比较好理解，横跨两个区域的比较难想到，其实不难，只要知道必须过的路径就好办了，横跨两个区域的最大子列必过-2和-1，只要计算以-2为尾的最大子列和，然后加上以-1为首的最大子列和即可。
时间复杂度分析：
共有N个数的话，前半部分的最大子列和与后半部分的最大子列和均为T(N/2)，横跨区域的最大子列和是从中间向左向右扫描，每个元素都被扫描一次，因此是N的常数倍，所以时间复杂度为o(N);
总时间复杂度是：
T(N)=2T(N/2)+cN,T(1)=O(1)。
所以T(N/2)=2T(N/4)+cN/2,带入原公式得
T(N)=2[2T(N/4)+cN/2]+cN
对此公式进行展开，一直展开至T()括号内的值为1，假设共展开了K次
则，T(N)=2^kO(1)+ck*N, N/2k=1,也就是N=2k,k=log2 N
所以T(N)=NO(1)+cN*log2 N
复杂度计算加法时，取最大的一个，所以取N*log2 N。
相比交优化算法的O(N^2)，分治算法的N*log2 N效率大大提高
网友评论