Medium

题目描述

给你一个整数数组 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 <= 10^5
  • -10^4 <= nums[i] <= 10^4

进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解题思路

这是一道经典的动态规划题目，有多种解法：

方法一：动态规划（Kadane算法） 这是最优解法。核心思想是：对于每个位置，我们需要决定是将当前元素加入之前的子数组，还是从当前元素重新开始一个新的子数组。

定义 dp[i] 为以第 i 个元素结尾的最大子数组和。状态转移方程为：

  • dp[i] = max(nums[i], dp[i-1] + nums[i])

这表示要么从当前元素重新开始，要么延续之前的子数组。为了节省空间，我们可以用一个变量来维护当前的最大子数组和。

方法二：分治法 将数组从中间分成两部分，最大子数组要么完全在左半部分，要么完全在右半部分，要么跨越中点。对于跨越中点的情况，需要分别计算从中点向左和向右的最大子数组和。

方法三：前缀和 通过维护前缀和数组，问题转化为找到两个前缀和的最大差值。

推荐使用动态规划解法，时间复杂度O(n)，空间复杂度O(1)，代码简洁且易理解。

代码实现

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = nums[0]
        
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            max_sum = max(max_sum, current_sum)
        
        return max_sum

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

var maxSubArray = function(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型动态规划解法分治法解法
时间复杂度O(n)O(n log n)
空间复杂度O(1)O(log n)

相关题目