LeetCode 53. Maximum Subarray

[Woodyiiiiiii]

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

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

---

可以和#20对比。

这属于线性DP问题，搞清楚dp[i]的含义是以第i个元素为结尾的子数组的最大和，状态转移函数是：

dp[i] = (nums[i] > dp[i - 1]) ? Math.max(nums[i], dp[i - 1] + nums[i]) : dp[i - 1] + nums[i];

如果当前元素比dp[i - 1]大，那么根据比较判断决定是否将旧的子数组抛弃，或者说是否把该元素命名为新的子数组的头；否则继续将该元素容纳进子数组中。
最后要获得结果，需要遍历整个数组。

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

时间和空间复杂度为O(n)。
当然可以进一步优化，使空间复杂度优化成常数级别。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n <= 0) {
            return 0;
        }
        int preSum = 0, maxSum = Integer.MIN_VALUE;
        
        for (int num : nums) {
            preSum = (preSum < num) ? Math.max(preSum + num, num) : preSum + num;
            maxSum = Math.max(preSum, maxSum);
        }
        
        return maxSum;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int preSum = 0, min = Integer.MAX_VALUE, res = Integer.MIN_VALUE;
        for (int num : nums) {
            preSum += num;
            res = Math.max(res, preSum - Math.min(0, min));
            min = Math.min(min, preSum);
        }
        return res;
    }
}

还有用分治法 Divide and Conquer Approach，这个解法的时间复杂度是 O(nlgn)。将数组分为左右子数组，从中间元素开始向左或向右分别遍历左子数组或右子数组。取得最大值。

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        return helper(nums, 0, nums.length - 1);
    }
    public int helper(int[] nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int lmax = helper(nums, left, mid - 1);
        int rmax = helper(nums, mid + 1, right);
        int mmax = nums[mid], t = mmax;
        for (int i = mid - 1; i >= left; --i) {
            t += nums[i];
            mmax = Math.max(mmax, t);
        }
        t = mmax;
        for (int i = mid + 1; i <= right; ++i) {
            t += nums[i];
            mmax = Math.max(mmax, t);
        }
        return Math.max(mmax, Math.max(lmax, rmax));
    }
}

三种解题思路:

1. DP
2. Kadane
3. 分治

类似题目:

• 152. Maximum Product Subarray
• 121. Best Time to Buy and Sell Stock
• 152. Maximum Product Subarray
• 198. House Robber

---

参考资料:

1. LeetCode原题
2. [LeetCode] 53. Maximum Subarray grandyang/leetcode#53
3. https://leetcode.com/problems/maximum-subarray/solutions/1595195/c-python-7-simple-solutions-w-explanation-brute-force-dp-kadane-divide-conquer/
4. 中文讲解1
5. 中文讲解2