跳转至

面试题 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)\)，其中 \(n\) 为数组长度。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
};

1
2
3
4
5
6
7
8
func maxSubArray(nums []int) int {
    ans, f := -1000000000, 0
    for _, x := range nums {
        f = max(f, 0) + x
        ans = max(ans, f)
    }
    return ans
}

1
2
3
4
5
6
7
8
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var ans = Int.min
        var currentSum = 0

        for x in nums {
            currentSum = max(currentSum, 0) + x
            ans = max(ans, currentSum)
        }

        return ans
    }
}

评论