剑指offer Dynamic Programming

剑指offer-连续子数组的最大和

Posted by franki on May 8, 2021

连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例:

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

思路

动态规划

1 定义两个变量 curSum greatestSum

2 遍历数组，每次更新curSum，当curSum累计的值小于0，curSum等于当前下标的值；并且对比curSum greatestSum，若curSum大于greatestSum，则更新greatestSum

3 循环结束并得到所求

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if (nums === null || nums.length === 0) {
        return null;
    }
    let nCurSum = 0;
    let nGreatestSum = Number.MIN_SAFE_INTEGER;
    for (let i=0; i<nums.length; i++) {
        if (nCurSum < 0) {
            nCurSum = nums[i];
        } else {
            nCurSum += nums[i];
        }
        if (nCurSum > nGreatestSum) {
            nGreatestSum = nCurSum;
        }
    }
    return nGreatestSum;
};

复杂度分析

  • 时间复杂度: 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