LeetCode-53 最大子数组和

ゝ一世哀愁。 2023-10-03 21:38 44阅读 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 条评论，44人围观）

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

相关阅读

相关 53. 最大子数组和

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

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

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

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

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

相关【LeetCode力扣】189 53 轮转数组 | 最大子数组和

目录 1、189. 轮转数组 1.1、题目介绍 1.2、解题思路 2、53. 最大子数组和 2.1、题目介绍 2.2、解题思路 ![0193ef4e293a

梦里梦外;/ 2024年02月20日 09:54/ 0 赞/ 16 阅读

相关 53. 最大子数组和

[53. 最大子数组和][53.] 难度简单4209收藏分享切换为英文接收动态反馈给你一个整数数组 `nums` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个

不念不忘少年蓝@/ 2023年10月11日 16:59/ 0 赞/ 12 阅读

相关 LeetCode_动态规划_简单_53.最大子数组和

目录 1.题目 2.思路 3.代码实现（Java） 4.扩展 1.题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数

缺乏、安全感/ 2023年10月06日 18:58/ 0 赞/ 23 阅读

相关 LeetCode-53 最大子数组和

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

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

相关 53. 最大子数组和

题目链接：https://leetcode-cn.com/problems/maximum-subarray/ > 给你一个整数数组 nums ，请你找出一个具有最大和的连续

缺乏、安全感/ 2023年02月08日 12:43/ 0 赞/ 11 阅读

相关 leetcode 53 最大子序和

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

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

相关 LeetCode53. 最大子序和

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

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

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

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

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