Java描述 LeetCode,53. Maximum Subarray

Java描述 LeetCode,53. Maximum Subarray,第1张

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,分治法我还不会,所以暂时先搁置吧。继续加油啊!河海哥,冲!如果错误,还请指证,谢谢大家~

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5438094.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-11
下一篇 2022-12-11

发表评论

登录后才能评论

评论列表(0条)

保存