Java描述 LeetCode，53. Maximum Subarray

Java描述 LeetCode，53. Maximum Subarray

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力。

1-1：题目

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

A subarray is a contiguous part of an array.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

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.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray

1-2：idea

这道题是简单题，我用dp解决了这个问题。我们可以用列表（就是手动模拟过程，填dp数组的值）的方式来对这个问题进行分析，首先dp状态dp[i]代表以nums[i]结尾的连续子数组的最大和为dp[i]。那么这个递推关系怎么来？我们在列表的时候，不难发现，如果dp[i-1]>=0的时候（dp[i-1]也就是子问题nums[0:i-1]这个数组的连续子数组最大和），才对当前dp[i]有益处，你可以想一下，如果小于0，我加上之后我自己反而变小了，肯定不如做自己了呀。注意，这里的nums[i]这个数字是必选的，我们只需要考虑子问题的最优解+自己nums[i] 是否能让这个和变大。所以递推式我们就可以写出来了。

• dp[i-1] >=0：dp[i] = dp[i-1] + nums[i]
• dp[i-1]<0：dp[i] = nums[i]

或者，对于dp[i]，有两种选择，可以选择做自己，也可以选择继承子问题的最优解，取最大值就好了也就是dp[i] = Math.max(dp[i-1] + nums[i], nums[i])。

1-3：代码

public static int maxSubArray(int[] nums) {
    int n = nums.length;

    int[] dp = new int[n]; // 0~n-1
    dp[0] = nums[0];
    int max = dp[0];
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] >= 0) {
            dp[i] = dp[i - 1] + nums[i];
        } else {
            dp[i] = nums[i];
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

代码可以用滚动数组的思想进行优化，应该比较简单，因为dp[i]只依赖于dp[i-1]，可以空间复杂度。

1-4：总结

这道题应该是简单的，我可算又能AC出一道了。由于我先攻的dp，分治法我还不会，所以暂时先搁置吧。继续加油啊！河海哥，冲！如果错误，还请指证，谢谢大家～