53. 最大子数组和

53. 最大子数组和 #

链接 #

53. 最大子数组和

题目 #

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

解答（动态规划） #

这个问题可以用动态规划（Dynamic Programming）来解决，其中一种著名的解法是“Kadane算法”。Kadane算法的思路是遍历数组，对于每一个元素，计算以该元素结尾的子数组的最大和。

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

pre 代表以当前元素结尾的子数组的最大和，ret 代表全局最大和。遍历数组时，如果 pre + x > x，说明 pre 对 x 有增益效果，否则说明 pre 对 x 无增益效果，因此 pre = max(pre + x, x)。在遍历过程中，ret 保持最大值。

上面的代码比较精简，下面的命名更友好一些，希望可以帮助你理解：

using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }
        
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.Max(maxSoFar, maxEndingHere);
        }
        
        return maxSoFar;
    }
    
    public static void Main() {
        Solution solution = new Solution();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = solution.MaxSubArray(nums);
        Console.WriteLine(result);  // 输出应为 6
    }
}

解答（分治法） #

还可以用分治法来解决，具体思路如下：

  1. 分解：将数组 nums 分割成两个子数组 nums_left 和 nums_right。
  2. 解决：递归地计算 nums_left 和 nums_right 中的最大子序和。
  3. 合并：比较三个子问题的解（nums_left 的最大子序和、nums_right 的最大子序和以及 nums_left 和 nums_right 合并后的最大子序和），取最大值。

在实现时，需要注意子问题的划分方式。由于我们需要比较三个子问题的解，因此可以在数组中间位置将数组分为两部分，同时也要考虑跨越中点的子数组。

下面是一个分治法解决这个问题的 Python 代码示例：

def maxSubArray(nums):
    def maxSubArrayHelper(nums, left, right):
        if left == right:
            return nums[left], nums[left]
        
        mid = (left + right) // 2
        # 计算左子数组的最大子序和
        left_max = max(maxSubArrayHelper(nums, left, mid),
                       maxSubArrayHelper(nums, mid + 1, right))
        
        # 计算包含中点的最大子序和
        mid_max = nums[mid]
        left_sum = mid_max
        right_sum = mid_max
        
        for i in range(mid, left - 1, -1):
            left_sum = max(nums[i] + left_sum, left_sum)
        
        for i in range(mid + 1, right + 1):
            right_sum = max(nums[i] + right_sum, right_sum)
        
        # 合并结果，返回三个子问题的最大值
        return max(left_max, left_sum + right_sum)
    
    return maxSubArrayHelper(nums, 0, len(nums) - 1)
# 示例
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 输出： 6

这段代码中，maxSubArrayHelper 函数是一个递归函数，它接受当前子数组的左右边界，并返回该子数组中的最大子序和以及子数组本身的最大子序和。在递归的最深层，它将问题分解为两个子问题并直接返回子问题的解。在向上返回的过程中，它合并子问题的解以得到最终结果。

需要注意的是，这种分治法的时间复杂度是 O(n log n)，空间复杂度也是 O(log n)，因为它需要递归地遍历数组，并且每次递归会使用一定量的栈空间。在处理大数据集时，这种方法的效率可能不如使用动态规划的方法。

计算包含中点的最大子序和的过程：

为了计算包含中点的最大子序和，我们需要分别从中间点向左右两边扩展，计算以中间点为中点的最大子数组和。这里有两个步骤：

  1. 从中间点向左扫描：从中间点开始向左扫描，累加扫描过的元素值，如果累加的和大于当前的最大和，则更新最大和。这样做的目的是为了找到包含中间点且最左边延伸到中间点左侧的最大子数组和。
  2. 从中间点向右扫描：同样从中间点开始向右扫描，累加扫描过的元素值，并且如果累加的和大于当前的最大和，则更新最大和。这一步是为了找到包含中间点且最右边延伸到中间点右侧的最大子数组和。

最后，将中间点的元素值与这两步得到的最大和相加，因为中间点的元素值被计算了两次（一次在左边，一次在右边），所以最终的跨越中点的最大子数组和就是这两部分和加上中间点的元素值。

解答（前缀和） #

使用前缀和寻找最大子数组和的基本思路是，对于每个可能的起始位置，找到最大的结束位置，使得从起始位置到结束位置的子数组和最大。这可以通过维护一个最小前缀和来实现，因为任何子数组的和可以通过两个前缀和的差来计算。如果我们知道最小的前缀和，那么我们可以通过当前的前缀和减去最小的前缀和来得到最大的子数组和。

public class Solution {
    public int MaxSubArray(int[] nums)
    {
        int n = nums.Length;
        int[] prefixSum = new int[n + 1];
        int minPrefixSum = 0;
        int maxSum = int.MinValue;
        // 计算前缀和
        for (int i = 1; i <= n; i++)
        {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        // 遍历前缀和数组，寻找最大子数组和
        for (int i = 1; i <= n; i++)
        {
            // 更新最大子数组和
            maxSum = Math.Max(maxSum, prefixSum[i] - minPrefixSum);
            // 更新最小前缀和
            minPrefixSum = Math.Min(minPrefixSum, prefixSum[i]);
        }
        return maxSum;
    }
}
Edit Edit this page