LeetCode 剑指 Offer 42. 连续子数组的最大和

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（Kadane 算法，推荐）
2. 解法二：分治
相似题目

题目描述

✅ 剑指 Offer 42. 连续子数组的最大和

思路分析

解法一：动态规划（Kadane 算法，推荐）

核心思路：

定义 dp[i] 为以第 i 个元素结尾的连续子数组的最大和

状态转移：dp[i] = max(dp[i-1] + nums[i], nums[i])，即要么将 nums[i] 接在前一段之后，要么以 nums[i] 重新开始

若 dp[i-1] < 0，则舍弃前面的子数组，从 nums[i] 重新开始更优

用滚动变量 pre 替代数组，将空间压缩至 O(1)

遍历过程中维护全局最大值 res

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，只需一次线性遍历

空间复杂度：O(1)，仅使用常数级别的额外变量

class Solution {
    public int maxSales(int[] nums) {
        // pre 表示以当前元素结尾的子数组最大和，res 记录全局最大值
        int pre = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 若前一段最大和为负，则从当前元素重新开始
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
        }
        return res;
    }
}

func maxSales(nums []int) int {
    // pre 表示以当前元素结尾的子数组最大和，res 记录全局最大值
    pre, res := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        // 若前一段最大和为负，则从当前元素重新开始
        pre = max(pre+nums[i], nums[i])
        res = max(res, pre)
    }
    return res
}

解法二：分治

核心思路：

将数组从中间分为左右两半，最大子数组和有三种情况：

完全在左半部分

完全在右半部分

跨越中点（左半部分的后缀最大和 + 右半部分的前缀最大和）

递归求解左右子问题，与跨越中点的情况取最大值

跨越中点时，从中点向左扫描求最大后缀和，向右扫描求最大前缀和

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度，递归深度为 O(log n)，每层合并 O(n)

空间复杂度：O(log n)，递归调用栈深度为 O(log n)

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

    private int divideAndConquer(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        // 分别求左半、右半的最大子数组和
        int leftMax = divideAndConquer(nums, left, mid);
        int rightMax = divideAndConquer(nums, mid + 1, right);
        // 求跨越中点的最大子数组和
        int crossMax = crossSum(nums, left, right, mid);
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    private int crossSum(int[] nums, int left, int right, int mid) {
        // 从中点向左扫描，求最大后缀和
        int leftSum = Integer.MIN_VALUE, sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }
        // 从中点向右扫描，求最大前缀和
        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }
        return leftSum + rightSum;
    }
}

func maxSales(nums []int) int {
    return divideAndConquer(nums, 0, len(nums)-1)
}

func divideAndConquer(nums []int, left, right int) int {
    if left == right {
        return nums[left]
    }
    mid := left + (right-left)/2
    // 分别求左半、右半的最大子数组和
    leftMax := divideAndConquer(nums, left, mid)
    rightMax := divideAndConquer(nums, mid+1, right)
    // 求跨越中点的最大子数组和
    crossMax := crossSum(nums, left, right, mid)
    return max(max(leftMax, rightMax), crossMax)
}

func crossSum(nums []int, left, right, mid int) int {
    // 从中点向左扫描，求最大后缀和
    leftSum, sum := math.MinInt64, 0
    for i := mid; i >= left; i-- {
        sum += nums[i]
        if sum > leftSum {
            leftSum = sum
        }
    }
    // 从中点向右扫描，求最大前缀和
    rightSum, sum := math.MinInt64, 0
    for i := mid + 1; i <= right; i++ {
        sum += nums[i]
        if sum > rightSum {
            rightSum = sum
        }
    }
    return leftSum + rightSum
}

相似题目

题目	难度	考察点
53. 最大子数组和	中等	动态规划、Kadane 算法
152. 乘积最大子数组	中等	动态规划、维护最大最小值
918. 环形子数组的最大和	中等	动态规划、最大和+最小和
1749. 任意子数组和的绝对值的最大值	中等	动态规划、最大子数组和变种
面试题 17.24. 最大子矩阵	困难	动态规划、压缩行降维
363. 矩形区域不超过 K 的最大数值和	困难	动态规划、前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/84853285