专栏首页YuanXinLeetCode 53.最大子序列和 - JavaScript

LeetCode 53.最大子序列和 - JavaScript

题目描述:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

例如对于 [-2,1,-3,4,-1,2,1,-5,4]来说,连续子数组 [4,-1,2,1] 的和最大,为 6。

虽然这题在 leetcode 上标注的是「简单」难度,但是解法有 4 种,并且都非常具有代表性。比较容易想到的是基础的动态规划法。

解法 1:动态规划

定义状态数组dp[i]的含义:数组中元素下标为[0, i]的连续子数组最大和。

状态转移的过程如下:

  • 初始情况:dp[0] = nums[0]
  • nums[i] > 0,那么 dp[i] = nums[i] + dp[i - 1]
  • nums[i] <= 0,那么 dp[i] = nums[i]

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/maximum-subarray/
// 原文地址:https://xxoo521.com/2020-03-09-max-sub-sum/
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    const dp = [];

    let res = (dp[0] = nums[0]);
    for (let i = 1; i < nums.length; ++i) {
        dp[i] = nums[i];
        if (dp[i - 1] > 0) {
            dp[i] += dp[i - 1];
        }
        res = Math.max(res, dp[i]);
    }
    return res;
};

时间复杂度和空间复杂度都是O(N)

解法 2:原地进行动态规划

解法 1 中开辟了 dp 数组。其实在原数组上做修改,用nums[i]来表示dp[i]。所以解法 1 的代码可以优化为:

// ac地址:https://leetcode-cn.com/problems/maximum-subarray/
// 原文地址:https://xxoo521.com/2020-03-09-max-sub-sum/
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let res = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        if (nums[i - 1] > 0) {
            nums[i] += nums[i - 1];
        }
        res = Math.max(res, nums[i]);
    }
    return res;
};

不用开辟额外空间,所以空间复杂度降为O(1)

解法 3:贪心法

贪心法的题目比较少见,而且一般都比较难证明。本题的贪心法的思路是:在循环中找到不断找到当前最优的和 sum。

注意:sum 是 nums[i]sum + nums[i]中最大的值。这种做法保证了 sum 是一直是针对连续数组算和。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/maximum-subarray/
// 原文地址:https://xxoo521.com/2020-03-09-max-sub-sum/
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = (sum = nums[0]);
    for (let i = 1; i < nums.length; ++i) {
        sum = Math.max(nums[i], sum + nums[i]);
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
};

空间复杂度为O(1),时间复杂度为O(N)

解法 4: 分治法

分治法的做题思路是:先将问题分解为子问题;解决子问题后,再将子问题合并,解决主问题。

使用分治法解本题的思路是:

  • 将数组分为 2 部分。例如 [1, 2, 3, 4] 被分为 [1, 2][3, 4]
  • 通过递归计算,得到左右两部分的最大子序列和是 lsum,rsum
  • 从数组中间开始向两边计算最大子序列和 cross
  • 返回 max(lsum, cross, rsum)

整体过程可以参考来自 Leetcode 官方题解的图:

可以看到,分治法可行的关键的是:最大子序列和只可能出现在左子数组、右子数组或横跨左右子数组 这三种情况下。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/maximum-subarray/
// 原文地址:https://xxoo521.com/2020-03-09-max-sub-sum/

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @param {number} mid
 * @return {number}
 */
function crossSum(nums, left, right, mid) {
    if (left === right) {
        return nums[left];
    }

    let leftMaxSum = Number.MIN_SAFE_INTEGER;
    let leftSum = 0;
    for (let i = mid; i >= left; --i) {
        leftSum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, leftSum);
    }

    let rightMaxSum = Number.MIN_SAFE_INTEGER;
    let rightSum = 0;
    for (let i = mid + 1; i <= right; ++i) {
        rightSum += nums[i];
        rightMaxSum = Math.max(rightMaxSum, rightSum);
    }

    return leftMaxSum + rightMaxSum;
}

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
function __maxSubArray(nums, left, right) {
    if (left === right) {
        return nums[left];
    }

    const mid = Math.floor((left + right) / 2);
    const lsum = __maxSubArray(nums, left, mid);
    const rsum = __maxSubArray(nums, mid + 1, right);
    const cross = crossSum(nums, left, right, mid);

    return Math.max(lsum, rsum, cross);
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    return __maxSubArray(nums, 0, nums.length - 1);
};

时间复杂度是O(NlogN)。由于递归调用,所以空间复杂度是O(logN)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 287.寻找重复数 - JavaScript

    题目描述:给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复...

    心谭博客
  • 剑指offer - 把数组排成最小的数 - JavaScript

    题目描述:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

    心谭博客
  • 【剑指offer:和为s的两个数字】双指针

    题目描述:输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,则输出任意一对即可。

    心谭博客
  • (美团)动态规划,打家劫舍!

    给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

    程序员小浩
  • 【一天一大 lee】翻转对 (难度:困难) - Day20201128

    给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

    前端小书童
  • Find Peak Element

    Tyan
  • 移动零

    一份执着✘
  • leetcode158|数组中的k-diffs数对

    给定一个整数数组和一个整数 k,你需要在数组里找到不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目。

    码农王同学
  • LeetCode48|三数之和

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三...

    码农王同学
  • 【leetcode刷题】T162-打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    木又AI帮

扫码关注云+社区

领取腾讯云代金券