Maximum Subarray

Leetcode-Algorithm-Divide and Conquer-53

例子： 给定数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，那么和最大的连续子数组是[4, -1, 2, 1]，和为6。

题解：

方法1：（动态规划） 迭代数组中的每一个数，把它们逐一加起来。把最终结果的和设为res，迭代过程的和设为sum。令res等于第一个元素，每加一个数，可能出出现3种情况：①sum增大；当sum大于res时，由于是连续元素相加得到的sum，所以符合连续子数组最大和，因此令res等于sum；②sum减少，小于res，但sum仍大于0，保留res的取值，由于sum大于0，进入下一次迭代加上下一个元素后有可能大于res，因此跳到下一个迭代；③sum减少到小于0，无论后面加多少个元素，都会比后面元素之和要少，因此重新计算sum，令sum等于0。保留res表示之前连续元素的最大和。在每次迭代中对以上情况做相应处理，最后的res就是答案。

代码：

分析： 由于只需迭代一次数组元素，因此时间复杂度为O(n)$O(n)$。

方法2：（分治法） 首先，令连续子数组的最大和为res，那么和最大的连续子数组的位置有三种可能： ①在数组的左半部分，由于和是最大的，所有比右半部分以及中央部分元素之和要大。 ②在数组的右半部分，同理，比左半部分以及中间部分元素之和要大。 ③位于数组的中间部位，那么通过从数组中央元素往数组两头计算的最大和leftmax+rightmax（要求逐一相加元素），会比左右两半部分的连续子数组最大和leftres、rightres都大。 同理，当连续子数组在数组的左右两部分时，可以继续上述步骤。

代码：

分析： 由上述分析可知，输入规模在每次递归都减半，而且需要计算两个部分，对两部分的合并处理需要O(n)$O(n)$步，因此，可得下面的公式：T(n)=2T(n/2)+O(n) $$T(n)=2T(n/2)+O(n)$$ 所以通过大师定理计算得时间复杂度为：O(nlogn) $$O(nlogn)$$