最大子序和

Tips

题目类型: Dynamic Programming, Greedy

题目

给定一个整数数组 nums, 找到一个具有最大和的连续子数组(子数组最少包含一个元素), 返回其最大和.

提示:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

示例

输入: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

输出: 6

解释: 连续子数组 [4, -1, 2, 1] 的和最大, 为 6.

题解

JavaScript - Kadane
JavaScript - 动态规划
JavaScript - 贪心
Rust

Kadane 算法(Kadane's algorithm)是一种用于解决最大子数组和问题的动态规划算法.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let maxEndingHere = nums[0]
  let maxSoFar = nums[0]

  for (let i = 1; i < nums.length; i++) {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i])
    maxSoFar = Math.max(maxSoFar, maxEndingHere)
  }

  return maxSoFar
}

dp[i - 1] + nums[i], 即 nums[i] 加入当前连续子序列和
nums[i], 即从 nums[i] 起计算当前连续子序列和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  const n = nums.length
  const dp = new Array(n).fill(0)
  dp[0] = nums[0]

  let max = nums[0]
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
    max = Math.max(max, dp[i])
  }

  return max
}

sum 为局部(也就是子数组)的累加和, 如果 sum 为负数或 0, 说明以前的累加和应该被废弃(毕竟越加越小); 如果 sum > 0, 前面的累加和就可以被复用. 让 ans 和 sum 比较, 找出最大的即可.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let ans = nums[0]
  let sum = 0

  for (const num of nums) {
    if (sum > 0) {
      sum += num
    } else {
      sum = num
    }

    ans = Math.max(ans, sum)
  }
  return ans
}

use std::cmp;

pub fn max_sub_array(nums: Vec<i32>) -> i32 {
    let mut ans = nums[0];
    let mut sum = 0;

    for num in nums {
        if sum > 0 {
            sum += num;
        } else {
            sum = num;
        }

        ans = cmp::max(ans, sum);
    }

    ans
}

题目​

题解​

题目

题解