Heading

53.最大子数组和 (opens new window)

Tags: algorithms bloomberg linkedin microsoft array divide-and-conquer dynamic-programming

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (55.22%)
• Likes: 6594
• Dislikes: -
• Total Accepted: 1.7M
• Total Submissions: 3M
• Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'

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

子数组 是数组中的一个连续部分。

 

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

 

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

/*
 * @lc app=leetcode.cn id=53 lang=javascript
 *
 * [53] 最大子数组和
 * 动态规划
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  if (nums.length < 1) {
    return 0
  }

  // f(n) = max(f(n-1)+nums(n),nums(n));
  let max = nums[0]
  const dp = [nums[0]]
  for (let i = 1; i < nums.length; i++) {
    if (dp[i - 1] + nums[i] > nums[i]) {
      dp[i] = dp[i - 1] + nums[i]
    } else {
      dp[i] = nums[i]
    }
    if (dp[i] > max) {
      max = dp[i]
    }
  }
  return max
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=53 lang=javascript
 *
 * [53] 最大子数组和
 * 贪心
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  if (nums.length < 1) {
    return 0
  }

  let maxSum = nums[0]
  let currentSum = nums[0]
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(currentSum + nums[i], nums[i])
    maxSum = Math.max(currentSum, maxSum)
  }
  return maxSum
}
// @lc code=end