LC-最大子序和

发表于 更新于 分类于

题目描述

最大子序和

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

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

代码实现

下面这个解法的思想就是求各个位置的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let prev = 0;
  let theMax = -Number.MAX_VALUE;
  for(let num of nums) {
    prev = Math.max(prev + num, num);
    theMax = Math.max(theMax, prev);
  }
  return theMax;
};