Leetcode 题目解析之 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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

curSum存储数组当前的和，maxSum存储数组中连续最大的和。

假设数组是−2,1,−3,4,−1,2,1,−5,4，首先curSum = -2, maxSum = -2。

1. 当i=1时，对于数组-2,1，curSum + nums1 = -1, 小于nums1 = 1。所以以后-2就可以舍弃，计算curSum时就从i=1开始。
2. 当i=2时，对于数组-2,1,-3，curSum + nums2 = -2, 大于nums2 = -3。虽然没有比原来大，但是至少比nums2大，对于以后计算更接近最优解。
3. 以此类推。

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