Question

面试题 42. 连续子数组的最大和

题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

 

示例1:

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

 

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

注意：本题与主站 53 题相同：https://leetcode.cn/problems/maximum-subarray/

 

解法

方法一：动态规划

我们定义 $f[i]$ 表示以第 $i$ 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

$$ \max_{0 \leq i \leq n-1} f[i] $$

那么我们如何求 $f[i]$ 呢？我们可以考虑 $nums[i]$ 单独成为一段还是加入 $f[i-1]$ 对应的那一段，这取决于 $nums[i]$ 和 $f[i-1] + nums[i]$ 哪个大，我们希望获得一个比较大的，于是可以写出这样的状态转移方程：

$$ f[i] = \max(f[i-1] + nums[i], nums[i]) $$

或者可以写成这样：

$$ f[i] = \max(f[i-1], 0) + nums[i] $$

我们可以不用开一个数组来存储所有的计算结果，而是只用两个变量 $f$ 和 $ans$ 来维护对于每一个位置 $i$ 我们的最大值，这样我们可以省去空间复杂度的开销。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组长度。

class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
    ans, f = -inf, 0
    for x in nums:
      f = max(f, 0) + x
      ans = max(ans, f)
    return ans

class Solution {
  public int maxSubArray(int[] nums) {
    int ans = Integer.MIN_VALUE;
    int f = 0;
    for (int x : nums) {
      f = Math.max(f, 0) + x;
      ans = Math.max(ans, f);
    }
    return ans;
  }
}

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int ans = INT_MIN;
    int f = 0;
    for (int& x : nums) {
      f = max(f, 0) + x;
      ans = max(ans, f);
    }
    return ans;
  }
};

func maxSubArray(nums []int) int {
  ans, f := -1000000000, 0
  for _, x := range nums {
    f = max(f, 0) + x
    ans = max(ans, f)
  }
  return ans
}

function maxSubArray(nums: number[]): number {
  let res = nums[0];
  for (let i = 1; i < nums.length; i++) {
    nums[i] = Math.max(nums[i], nums[i - 1] + nums[i]);
    res = Math.max(res, nums[i]);
  }
  return res;
}

impl Solution {
  pub fn max_sub_array(mut nums: Vec<i32>) -> i32 {
    let mut res = nums[0];
    for i in 1..nums.len() {
      nums[i] = nums[i].max(nums[i - 1] + nums[i]);
      res = res.max(nums[i]);
    }
    res
  }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let ans = -1e10;
  let f = 0;
  for (const x of nums) {
    f = Math.max(f, 0) + x;
    ans = Math.max(ans, f);
  }
  return ans;
};

public class Solution {
  public int MaxSubArray(int[] nums) {
    int ans = -1000000000;
    int f = 0;
    foreach (int x in nums) {
      f = Math.Max(f, 0) + x;
      ans = Math.Max(ans, f);
    }
    return ans;
  }
}