Voyz's Studio.

LeetCode算法笔记--最大子序和

算法题 热题HOT100 动态规划
字数统计: 232阅读时长: 1 min
2020/12/15 Share

LeetCode算法笔记–Day42

53. Maximum Subarray

题目：

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

example
input: [-2,1,-3,4,-1,2,1,-5,4]
output: 6

Analyze：

方法一：动态规划

  • 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
  • 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
  • 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
  • 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
  • 时间复杂度：O(n)O(n)

My Answer：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let sum = 0,
        res = nums[0];

    nums.forEach((num)=>{
        if(sum <= 0){
            sum = num;
        }else {
            sum += num;
        }
        res = Math.max(res,sum)
    })

    return res;
};
CATALOG
  1. 1. LeetCode算法笔记–Day42
  2. 2. 53. Maximum Subarray
    1. 2.1. 题目：
    2. 2.2. Analyze：
      1. 2.2.1. 方法一：动态规划
    3. 2.3. My Answer：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa