LeetCode 53. Maximum Subarray

原题链接在这里：https://leetcode.com/problems/maximum-subarray/

题目：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

题解：

采用的是DP解法. 把原有问题拆成小问题. maxSubArray(int [] nums, int i). 表示到 [0,i]段最大的sub array. 前提是包括 i 元素.

maxSubArray(nums, i) = nums[i] + maxSubArray(nums, i-1) > 0 ? maxSubArray(nums, i-1) : 0.

同时维护全局最大值.

历史信息就是local[i-1] 和 global[i-1], 更新当前信息时先更新局部最优.

local[i] = Math.max(local[i-1]+nums[i], nums[i]), 有可能local[i-1]是负数，就直接取nums[i], 然后更新全局最优.

global[i] = Math.max(lcoal[i], global[i-1]), 要么是原来的全局最优，要么是局部最优，此时能涵盖所有解。如果全局最优不包含当前值，那么会被维护在global[i-1]中，若包含当前值，那么就是local[i].

Note: local, global的初始化是nums[0]. 不能初始化成0, 然后从i=1开始，比如[-1], Output:0, Expected:-1, 这种corner case 就会出错.

Time Complexity: O(n).n = nums.length.

Space: O(1).

AC Java:

public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length ==0){
            return 0;
        }
        int global = nums[0];
        int local = nums[0];
        for(int i = 1; i< nums.length; i++){
            local = Math.max(local + nums[i], nums[i]);
            global = Math.max(global, local);
        }
        return global;
    }
}

类似Maximum Product Subarray, House Robber, Best Time to Buy and Sell Stock., Longest Turbulent Subarray.

跟上Maximum Subarray II.

Reference: http://blog.csdn.net/linhuanmars/article/details/21314059