Question

53. 最大子数组和

English Version

题目描述

给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。

解法

方法一：动态规划

我们定义 $f[i]$ 表示以元素 $nums[i]$ 为结尾的连续子数组的最大和，初始时 $f[0] = nums[0]$，那么最终我们要求的答案即为 $\max_{0 \leq i < n} f[i]$。

考虑 $f[i]$，其中 $i \geq 1$，它的状态转移方程为：

$$ f[i] = \max { f[i - 1] + nums[i], nums[i] } $$

也即：

$$ f[i] = \max { f[i - 1], 0 } + nums[i] $$

由于 $f[i]$ 只与 $f[i - 1]$ 有关系，因此我们可以只用一个变量 $f$ 来维护对于当前 $f[i]$ 的值是多少，然后进行状态转移即可。答案为 $\max_{0 \leq i < n} f$。

时间复杂度 $O(n)$，其中 $n$ 为数组 $nums$ 的长度。我们只需要遍历一遍数组即可求得答案。空间复杂度 $O(1)$，我们只需要常数空间存放若干变量。

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

class Solution {
  public int maxSubArray(int[] nums) {
    int ans = nums[0];
    for (int i = 1, f = nums[0]; i < nums.length; ++i) {
      f = Math.max(f, 0) + nums[i];
      ans = Math.max(ans, f);
    }
    return ans;
  }
}

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int ans = nums[0], f = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
      f = max(f, 0) + nums[i];
      ans = max(ans, f);
    }
    return ans;
  }
};

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

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

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let [ans, f] = [nums[0], nums[0]];
  for (let i = 1; i < nums.length; ++i) {
    f = Math.max(f, 0) + nums[i];
    ans = Math.max(ans, f);
  }
  return ans;
};

public class Solution {
  public int MaxSubArray(int[] nums) {
    int ans = nums[0], f = nums[0];
    for (int i = 1; i < nums.Length; ++i) {
      f = Math.Max(f, 0) + nums[i];
      ans = Math.Max(ans, f);
    }
    return ans;
  }
}

方法二

class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
    def crossMaxSub(nums, left, mid, right):
      lsum = rsum = 0
      lmx = rmx = -inf
      for i in range(mid, left - 1, -1):
        lsum += nums[i]
        lmx = max(lmx, lsum)
      for i in range(mid + 1, right + 1):
        rsum += nums[i]
        rmx = max(rmx, rsum)
      return lmx + rmx

    def maxSub(nums, left, right):
      if left == right:
        return nums[left]
      mid = (left + right) >> 1
      lsum = maxSub(nums, left, mid)
      rsum = maxSub(nums, mid + 1, right)
      csum = crossMaxSub(nums, left, mid, right)
      return max(lsum, rsum, csum)

    left, right = 0, len(nums) - 1
    return maxSub(nums, left, right)

class Solution {
  public int maxSubArray(int[] nums) {
    return maxSub(nums, 0, nums.length - 1);
  }

  private int maxSub(int[] nums, int left, int right) {
    if (left == right) {
      return nums[left];
    }
    int mid = (left + right) >>> 1;
    int lsum = maxSub(nums, left, mid);
    int rsum = maxSub(nums, mid + 1, right);
    return Math.max(Math.max(lsum, rsum), crossMaxSub(nums, left, mid, right));
  }

  private int crossMaxSub(int[] nums, int left, int mid, int right) {
    int lsum = 0, rsum = 0;
    int lmx = Integer.MIN_VALUE, rmx = Integer.MIN_VALUE;
    for (int i = mid; i >= left; --i) {
      lsum += nums[i];
      lmx = Math.max(lmx, lsum);
    }
    for (int i = mid + 1; i <= right; ++i) {
      rsum += nums[i];
      rmx = Math.max(rmx, rsum);
    }
    return lmx + rmx;
  }
}