53.最大子数组和
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组 (子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
提示:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
**进阶:**如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
解法
1.动态规划
步骤
1,确定状态
2,找到转移公式
3,确定初始条件以及边界条件
4,计算结果。
定义
dp[i]
表示数组中前i+1
(注意这里的 i 是从 0 开始的)个元素构成的连续子数组的最大和。如果要计算前 i+1 个元素构成的连续子数组的最大和,也就是计算 dp[i],只需要判断 dp[i-1]是大于 0 还是小于 0。如果 dp[i-1]大于 0,就继续累加,dp[i]=dp[i-1]+num[i]。如果 dp[i-1]小于 0,我们直接把前面的舍弃,也就是说重新开始计算,否则会越加越小的,直接让 dp[i]=num[i]。所以转移公式如下
dp[i] = num[i] + max(dp[i - 1], 0);
- 边界条件判断,当 i 等于 0 的时候,也就是前 1 个元素,他能构成的最大和也就是他自己,所以
dp[0] = num[0];
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
const length = nums.length;
const dp = [];
dp[0] = nums[0];
let max = dp[0];
for (let i = 1; i < length; i++) {
dp[i] = Math.max(dp[i - 1], 0) + nums[i];
max = Math.max(dp[i], max);
}
return max;
};
申请了一个长度为 length 的数组,但在转移公式计算的时候,每次计算当前值的时候只会用到前面的那个值,再往前面就用不到了,这样实际上是造成了空间的浪费。这里不需要一个数组,只需要一个临时变量即可
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
const length = nums.length;
const dp = [];
let cur = nums[0];
let max = cur;
for (let i = 1; i < length; i++) {
cur = Math.max(cur, 0) + nums[i];
max = Math.max(cur, max);
}
return max;
};