暴力
解题思路
第一层 for 就是设置起始位置，第二层 for 循环遍历数组寻找最大值；
解法超时；
复杂度
-
时间复杂度：
O(n^2)； -
空间复杂度：
O(1)；
代码实现
var maxSubArray = function (nums) {
let res = -Infinity;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum = 0;
for (let j = i; j < nums.length; j++) {
sum += nums[j];
res = Math.max(res, sum);
}
}
return res;
};
贪心
解题思路
局部最优：当前 连续和 为负数的时候立刻放弃，从下一个元素重新计算 连续和 ，因为负数加上下一个元素 连续和 只会越来越小；
局部最优的情况下，并记录最大的 连续和 ，可以推出全局最优；
遍历 nums 从头开始用 sum 累积，如果 sum 一旦加上 nums[i] 变为负数，那么就应该从 nums[i+1] 开始从 0 累积 sum 了，因为已经变为负数的 sum ，只会拖累总和；
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(1)；
代码实现
var maxSubArray = function (nums) {
let res = -Infinity;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
// 更新最大值
if (sum > res) res = sum; // 等价 => res = Math.max(res, sum);
// 重置区间的起始位置，sum < 0，会拖累总和，则需要重新选取位置
if (sum <= 0) sum = 0;
}
return res;
};
动态规划
解题思路
先欠着
复杂度
代码实现
// 时间复杂度：O(N)
// 空间复杂度：O(N)
const maxSubArray = nums => {
// 数组长度，dp初始化
const dp = [nums[0]];
const len = nums.length;
// 最大值初始化为dp[0]
let max = dp[0];
for (let i = 1; i < len; i++) {
// 表示以 nums[i] 结尾 的 连续 子数组的最大和
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
// 更新最大值
max = Math.max(max, dp[i]);
}
return max;
};
// 时间复杂度：O(N)
// 空间复杂度：O(1)
const maxSubArray = nums => {
let sum = nums[0];
let max = nums[0];
for (let i = 1; i < nums.length; i++) {
sum = Math.max(sum + nums[i], nums[i]);
// 更新最大值
max = Math.max(max, sum);
}
return max;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 376. 摆动序列
上一篇
评论
