[LeetCode]Maximum Subarray

是一道题的解法可以带出十道题解法的题目，首先我们定义两个变量，localMax[i]为以i结尾的subarray中最大的值，globalMax[i]定义为[0, i]范围中最大的subarray(subarray不一定需要已i结尾)。递推表达式是：

• localMax[i] = max(localMax[i - 1] + A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);

根据这个表达式我们只需要从左向右扫一遍就可以了，时间复杂度O(n)，然后空间可以优化到O(1)，代码如下：

另外还有个divide and conquer，分成两半，找左边右边和跨过中间的max subarray中的最大值，中间的是很好找的，左边一直扩展记录最大值，右边同样的，然后返回左边最大值加上右边最大值，线性时间可以找到，所以总的时间复杂度是O(n log n)，代码如下：