跳到主要内容

53.最大子数组和

链接：53.最大子数组和
难度：Medium
标签：数组、分治、动态规划
简介：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

题解 1 - javascript​

  • 编辑时间：2020-05-03
  • 执行用时：64ms
  • 内存消耗：35.4MB
  • 编程语言：javascript
  • 解法介绍：遍历数组，若前一项大于 0 则当前项+=前一项，最后获取数组中的最大值。
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  const len = nums.length;
  let max = nums[0];
  if (len === 1) return nums[0];
  for (let i = 1; i < len; i++) {
    if (nums[i - 1] > 0) nums[i] += nums[i - 1];
    if (max < nums[i]) max = nums[i];
  }
  return max;
};

题解 2 - javascript​

  • 编辑时间：2020-05-07
  • 执行用时：80ms
  • 内存消耗：35.2MB
  • 编程语言：javascript
  • 解法介绍：分治法。
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  if (nums === null || nums.length === 0) return 0;
  return _maxSubArray(nums, 0, nums.length);
  function _maxSubArray(nums, begin, end) {
    if (end - begin < 2) return nums[begin];
    const mid = (begin + end) >> 1;
    let leftMax = -Infinity;
    let leftSum = 0;
    for (let i = mid - 1; i >= begin; i--) {
      leftSum += nums[i];
      leftMax = Math.max(leftMax, leftSum);
    }
    let rightMax = -Infinity;
    let rightSum = 0;
    for (let i = mid; i < end; i++) {
      rightSum += nums[i];
      rightMax = Math.max(rightMax, rightSum);
    }
    const max = leftMax + rightMax;
    return Math.max(max, _maxSubArray(nums, begin, mid), _maxSubArray(nums, mid, end));
  }
};

题解 3 - javascript​

  • 编辑时间：2020-05-10
  • 执行用时：64ms
  • 内存消耗：35.9MB
  • 编程语言：javascript
  • 解法介绍：动态规划，递推，dp[i]=以 nums[i]结尾的子序列和。
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  const len = nums.length;
  if (nums == null || len == 0) return 0;
  const dp = [nums[0]];
  let max = dp[0];
  for (let i = 1; i < len; i++) max = Math.max(max, (dp[i] = Math.max(0, dp[i - 1]) + nums[i]));
  return max;
};

题解 4 - javascript​

  • 编辑时间：2020-05-10
  • 执行用时：92ms
  • 内存消耗：34.8MB
  • 编程语言：javascript
  • 解法介绍：跟题解 3 思路一样，优化空间。
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  const len = nums.length;
  if (nums == null || len == 0) return 0;
  let max = (dp = nums[0]);
  for (let i = 1; i < len; i++) max = Math.max(max, (dp = Math.max(0, dp) + nums[i]));
  return max;
};

题解 5 - typescript​

  • 编辑时间：2021-05-14
  • 执行用时：92ms
  • 内存消耗：40.5MB
  • 编程语言：typescript
  • 解法介绍：利用前缀和进行快速相减。
function maxSubArray(nums: number[]): number {
  const len = nums.length;
  const prefixSumList = [0];
  for (let i = 1; i <= len; i++) prefixSumList[i] = prefixSumList[i - 1] + nums[i - 1];
  let min = prefixSumList[0];
  let ans = nums[0];
  for (let i = 1; i <= len; i++)
    ans = Math.max(prefixSumList[i] - (min = Math.min(min, prefixSumList[i - 1])), ans);
  return ans;
}

题解 6 - typescript​

  • 编辑时间：2021-07-17
  • 执行用时：4620ms
  • 内存消耗：46.1MB
  • 编程语言：typescript
  • 解法介绍：前缀和。
function maxSubArray(nums: number[]): number {
  let num = 0;
  const len = nums.length;
  const sums = [0, ...nums.map(v => (num += v))];
  let ans = -Infinity;
  for (let i = 0; i < len; i++) {
    ans = Math.max(ans, nums[i]);
    const sum = sums[i + 1];
    for (let j = 0; j < i; j++) {
      const num = sum - sums[j];
      ans = Math.max(ans, num);
    }
  }
  return ans;
}

题解 7 - typescript​

  • 编辑时间：2021-07-17
  • 执行用时：88ms
  • 内存消耗：47.6MB
  • 编程语言：typescript
  • 解法介绍：前缀和。
function maxSubArray(nums: number[]): number {
  let num = 0;
  const len = nums.length;
  const sums = [0, ...nums.map(v => (num += v))];
  let min = 0;
  let ans = -Infinity;
  for (let i = 0; i < len; i++) {
    const sum = sums[i + 1];
    ans = Math.max(ans, sum - min, nums[i]);
    min = Math.min(min, sum);
  }
  return ans;
}

题解 8 - typescript​

  • 编辑时间：2021-07-22
  • 执行用时：72ms
  • 内存消耗：39.6MB
  • 编程语言：typescript
  • 解法介绍：取最大值。
function maxSubArray(nums: number[]): number {
  let ans = -Infinity;
  let max = 0;
  for (let i = 0; i < nums.length; i++) {
    if (max > 0) max += nums[i];
    else max = nums[i];
    ans = Math.max(ans, max);
  }
  return ans;
}

题解 9 - typescript​

  • 编辑时间：2021-07-22
  • 执行用时：72ms
  • 内存消耗：39.9MB
  • 编程语言：typescript
  • 解法介绍：单调递增队列。
function maxSubArray(nums: number[]): number {
  if (nums.length === 1) return nums[0];
  const sums = [0];
  nums.forEach((num, i) => sums.push(sums[i] + num));
  const queue: number[] = [0];
  let ans = -Infinity;
  for (let i = 1; i <= nums.length; i++) {
    const num = sums[i];
    ans = Math.max(ans, num - queue[0]);
    while (queue.length && queue[queue.length - 1] > num) queue.pop();
    queue.push(num);
  }
  return ans;
}

题解 10 - typescript​

  • 编辑时间：2021-09-04
  • 执行用时：75ms
  • 内存消耗：39.5MB
  • 编程语言：typescript
  • 解法介绍：前缀和，减去前面前缀和的最小值。
function maxSubArray(nums: number[]): number {
  const sums = [0];
  const n = nums.length;
  for (let i = 0; i < n; i++) sums.push(sums[sums.length - 1] + nums[i]);
  let ans = -Infinity;
  let min = 0;
  for (let i = 1; i <= n; i++) {
    ans = Math.max(sums[i] - min, ans);
    min = Math.min(min, sums[i]);
  }
  return ans;
}

题解 11 - cpp​

  • 编辑时间：2021-12-21
  • 执行用时：164ms
  • 内存消耗：66.1MB
  • 编程语言：cpp
  • 解法介绍：分治，求出左边最大值，右边最大值和中间最大值。
class Solution {
   public:
    int maxSubArray(vector<int>& nums) { return dfs(nums, 0, nums.size() - 1); }
    int dfs(vector<int>& nums, int l, int r) {
        if (l == r) return nums[l];
        int m = (l + r) >> 1, lmax = INT_MIN, rmax = INT_MIN, sum = 0;
        for (int i = m; i >= l; i--) {
            sum += nums[i];
            lmax = max(lmax, sum);
        }
        sum = 0;
        for (int i = m + 1; i <= r; i++) {
            sum += nums[i];
            rmax = max(rmax, sum);
        }
        return max(lmax + rmax, max(dfs(nums, l, m), dfs(nums, m + 1, r)));
    }
};

题解 12 - cpp​

  • 编辑时间：2021-12-21
  • 执行用时：100ms
  • 内存消耗：66MB
  • 编程语言：cpp
  • 解法介绍：遍历，每次求出前面的最大值。
class Solution {
   public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0], ans = sum;
        for (int i = 1; i < nums.size(); i++) {
            sum = max(0, sum) + nums[i];
            ans = max(ans, sum);
        }
        return ans;
    }
};

题解 13 - python​

  • 编辑时间：2023-11-20
  • 执行用时：168ms
  • 内存消耗：30.34MB
  • 编程语言：python
  • 解法介绍：遍历后记录前面的最小前缀和。
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf
        prev = 0
        sums = 0
        for num in nums:
            sums += num
            ans = max(ans, sums - prev)
            prev = min(prev, sums)
        return ans