leetcode Dynamic Programming

leetcode 53题

Posted by franki on June 17, 2021

leetcode 53题 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例1

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例2

输入：nums = [1]
输出：1

思路

方法一：动态规划

方法二：举例

代码

方法一：动态规划
const maxSubArray = (nums) => {
    const dp = [nums[0]];
    let res = dp[0];
    for (let i=1; i<nums.length; i++) {
        if (dp[i-1] < 0) {
            dp[i] = nums[i];
        } else {
            dp[i] = dp[i-1] + nums[i];
        }
        res = Math.max(res, dp[i]);
    }
    return res;
};

方法二：举例
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if (nums.length === 1) {
        return nums[0];
    }
    let maxValue = nums[0];
    let res = 0;
    for (let i=0; i < nums.length; i++) {
        res += nums[i];
        if (res > maxValue) {
            maxValue = res;
        }
        if (res < 0) {
            res = 0;
        }
    }
    return maxValue;
};

复杂度分析:

方法一：

  • 时间复杂度: O(N)
  • 空间复杂度：O(N)

方法二：

  • 时间复杂度: O(N)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS