剑指 Offer 42. 连续子数组的最大和
难度: e a s y \color{Green}{easy} easy
题目描述
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
- 1 < = a r r . l e n g t h < = 1 0 5 1 <= arr.length <= 10^5 1<=arr.length<=105
- − 100 < = a r r [ i ] < = 100 -100 <= arr[i] <= 100 −100<=arr[i]<=100
注意:本题与主站 53 题相同:https://leetcode-cn.com/problems/maximum-subarray/
算法
常见解法 | 时间复杂度 |
---|---|
暴力搜索 | O ( n 2 ) O(n^2) O(n2) |
分治思想 | O ( n l o g n ) O(nlogn) O(nlogn) |
动态规划 | O ( n ) O(n) O(n) |
(动态规划)
- 状态定义: 设动态规划列表 d p dp dp , d p [ i ] dp[i] dp[i] 代表以元素 n u m s [ i ] nums[i] nums[i] 为结尾的连续子数组最大和。
为何定义最大和
dp[i]
中必须包含元素nums[i]
:保证dp[i]
递推到dp[i+1]
的正确性;如果不包含nums[i]
,递推时则不满足题目的 连续子数组 要求。
-
转移方程: 若 d p [ i − 1 ] ≤ 0 dp[i−1]≤0 dp[i−1]≤0 ,说明 d p [ i − 1 ] dp[i−1] dp[i−1] 对 d p [ i ] dp[i] dp[i] 产生负贡献,即 d p [ i − 1 ] + n u m s [ i ] dp[i−1]+nums[i] dp[i−1]+nums[i] 还不如 n u m s [ i ] nums[i] nums[i] 本身大。
- 当 d p [ i − 1 ] > 0 dp[i−1]>0 dp[i−1]>0 时:执行 d p [ i ] = d p [ i − 1 ] + n u m s [ i ] dp[i]=dp[i−1]+nums[i] dp[i]=dp[i−1]+nums[i] ;
- 当 d p [ i − 1 ] ≤ 0 dp[i−1]≤0 dp[i−1]≤0 时:执行 d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i] ;
-
初始状态: d p [ 0 ] = n u m s [ 0 ] dp[0]=nums[0] dp[0]=nums[0],即以 n u m s [ 0 ] nums[0] nums[0] 结尾的连续子数组最大和为 n u m s [ 0 ] nums[0] nums[0] 。
-
返回值: 返回 d p dp dp 列表中的最大值,代表全局最大值。
复杂度分析
-
时间复杂度: O ( n ) O(n) O(n)。
-
空间复杂度 : O ( 1 ) O(1) O(1)
C++ 代码
使用 res
代表最终的答案,s
表示前 i - 1
项的值, 如果前 i - 1
项的值小于 0
,s
等于当前的数 num
,如果大于 0
, 说明可以加上当前的数字 num
,继续往后运算。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN, s = 0;
for (auto x : nums) {
if (s < 0) s = 0;
s += x;
res = max(res, s);
}
return res;
}
};
相关文章
- 【说站】js数组在头部或尾部插入元素的方法
- 剑指offer No.30 连续子数组的最大和
- 三刷”数组中的第K个最大元素“,我终于学会了堆排序
- 2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组,求剩下的数组,严格连续递增的子数组最大长度。n
- C语言数组初始化的三种方法[通俗易懂]
- 截断数组
- 【力扣/牛客刷题】136. 只出现一次的数字 || 75. 颜色分类 || 215. 数组中的第K个最大元素
- [PHP] PHP数组的实现哈希表(HashTable)结构详解编程语言
- Javascript中的Array(数组) 、{}(映射) 与JSON解析详解编程语言
- Js获取数组最大和最小值示例代码