LeetCode-53 最大子数组和

ゝ一世哀愁。 2023-10-03 21:38 11阅读 0赞

#### 问题描述 ####

给你一个整数数组`nums` ，请你找出一个具有最大和的**连续子数组**（子数组最少包含一个元素），返回其最大和。

> 示例  
> 输入：nums = \[-2,1,-3,4,-1,2,1,-5,4\]  
> 输出：6  
> 解释：连续子数组 \[4,-1,2,1\] 的和最大，为 6 。

这里注意的一个点是，**子数组** 与 **子序列**。我们通常这样认为子数组是数组的连续子集，即使数组的切片。而子序列是数组的任意子集，即可以有数组里任意元素组合而成。

#### 动态规划思路 ####

##### 状态定义 #####

定义一维的`dp`数组，dp\[i\]表示**下标为i结尾**的`nums`数组最大连续子数组和，并维护一个全局的最大值`res`。

##### 状态转移逻辑 #####

我们在累加元素时必须要考虑的是，如果累加当前元素`nums[i]`之后大于当前元素`nums[i]`，那么我们就更新子数组和为`dp[i-1]+nums[i]`。反之就得从当前元素`nums[i]`开始重新累加：  
`dp[i] = max(dp[i-1]+nums[i], nums[i])`

##### 初始值及特殊情况 #####

由于递推公式中有`i-1`，所以我们需要给`dp[0]`赋初始值`nums[0]`，一个数的数组子数组和就是他本身。遍历循环从`i=1`开始。

#### 代码 ####

public static int maxSubArray(int[] nums) {
        
            int res = nums[0];
            int[] dp = new int[nums.length+1];
            dp[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
        
                dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
                res = Math.max(dp[i], res);
            }
            return res;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 53. 最大子数组和

> 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 > 子数组:是数组中的一个连续部分。示例 1： >

╰半夏微凉°/ 2024年04月01日 15:00/ 0 赞/ 38 阅读

相关 LeetCode-53. 最大子数组和

目录动态规划题目来源 [53. 最大子数组和][53.] 动态规划 1.确定dp数组（dp table）以及下标的含义 dp\[i\

女爷i/ 2024年03月24日 08:28/ 0 赞/ 30 阅读

相关 LeetCode-53 最大子数组和

问题描述给你一个整数数组`nums` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 > 示例 > 输入：nums = \[-2,

ゝ一世哀愁。/ 2023年10月03日 21:38/ 0 赞/ 12 阅读

相关 LeetCode53. 最大子序和

难度：简单题目描述： > 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 ![在这里插入图片描述][water

Myth丶恋晨/ 2022年10月20日 05:29/ 0 赞/ 136 阅读

相关 leetcode 53 最大子序和

前言题目：[53. 最大子序和][53.] 参考题解：[最大子序和-代码随想录][-] -------------------- 提交代码 (残酷)思路：前

女爷i/ 2022年09月14日 09:49/ 0 赞/ 156 阅读

相关 Leetcode-53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例 1：输入：nums = [-2,1,-3,4,-1

我会带着你远行/ 2022年09月03日 13:18/ 0 赞/ 138 阅读

相关 LeetCode 53. 最大子序和

给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5

痛定思痛。/ 2022年05月17日 02:18/ 0 赞/ 166 阅读

相关 Leetcode53最大子序和

给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。输入: [-2,1,-3,4,-1,2,1,-5,4],

我就是我/ 2022年02月17日 02:23/ 0 赞/ 229 阅读

相关 LeetCode53. 最大子序和

题目描述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,

╰+攻爆jí腚メ/ 2021年10月19日 08:46/ 0 赞/ 285 阅读

相关 LeetCode : 53. Maximum Subarray 最大子数组和

试题 Given an integer array nums, find the contiguous subarray (containing at least one

古城微笑少年丶/ 2021年06月24日 16:10/ 0 赞/ 309 阅读