Voyz's Studio.

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

字数统计: 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: