问题：给定一个数组,找到一个连续的子数组,使得这个子数组的和最大。
举个例子，[1, -3, 2, 1, -1]的最大子数组是[2, 1]，其和为3。

Brute-force Solution

最容易想到的就是暴力解法，遍历所有可能的子数组，时间复杂度为O(n^2)。

public int maxSubArray(int[] nums) {
    int globalMax = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int currentMax = 0;
        for (int j = i; j < nums.length; j++) {
            currentMax += nums[j];
            globalMax = Math.max(globalMax, currentMax);
        }
    }
    return globalMax;
}

Kadane’s Algorithm

暴力虽然能解决问题，但我们还是要更优雅~
（这道题在leetcode上被标为easy，看题的时候提示有O(n)的解法，结果想了老半天也没解出来，唉o(╥﹏╥)o

Kadane算法可以优化到O(n)，怎么做到的呢？

Kadane算法被归为动态规划，终于有勇气揭开DP神秘的面纱~

动态规划(Dynamic programming)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。—— 维基百科

两种主要的DP实现方式：

Tabulation - 自底向上(Bottom Up)解决问题
Memoization - 自顶向下(Top Down)解决问题

这部分初次接触，还不太了解，先存几个Link:

Kadane算法思路

既然动态规划的中心思想就是分解问题，所以Kadane算法中至关重要的一步就是定义合适的子问题，并找到问题与子问题间的关系。
Kadane算法将子问题定义为：求以第i个元素结尾的最大子数组。
什么意思？举个例子：
假设有数组A:[a, b, c, d, e]，则：

以第0个元素结尾的最大子数组就是它自己：[a]
以第1个元素结尾的最大子数组可能是这些中的一个：[a, b], [b]
以第2个元素结尾的最大子数组可能是这些中的一个：[a, b, c], [b, c], [c]

考虑以第i个元素结尾的子数组，一定是以第i-1个元素结尾的子数组加上第i个元素组成的，由此可以推导出如下关系：

1 2	maxSum[0] = A[0]; // i = 0 maxSum[i] = A[i] + （maxSum[i-1] > 0 ? maxSum[i-1] : 0); // i > 0

也就是说，如果以第i-1个元素结尾的最大子数组和大于0，那么以第i个元素结尾的最大子数组就等于它前面的那部分加上它自己，否则就舍弃前面的部分，只剩它自己。

回到问题，maxSum这个数组中的每个元素就代表了以当前位置结尾的最大子数组和，取maxSum中的最大值就是整个数组的最大子数组和啦。

Kadane算法的完整实现如下：

public int maxSubArray(int[] nums) {
    int[] maxSum = new int[nums.length];
    maxSum[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        maxSum[i] = nums[i] + Math.max(0, maxSum[i-1]);
        max = Math.max(maxSum[i], max);
    }
    return max;
}

最后安利一个把MSP讲解得非常清晰的视频~Kadane’s Algorithm to Maximum Sum Subarray Problem

Maximum Subarray Problem & Kadane's Algorithm

Brute-force Solution

Kadane’s Algorithm

Kadane算法思路

参考资料