algorithms►leetcode

007-最大子数组和（Kadane算法）

最大子数组和（Kadane算法）

问题描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解决方案

方法一：暴力解法（不推荐）

检查所有可能的子数组，计算它们的和并找出最大值。

时间复杂度：O(n²)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
function maxSubArray(nums) {
    let maxSum = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        let currentSum = 0;
        for (let j = i; j < nums.length; j++) {
            currentSum += nums[j];
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    return maxSum;
}

方法二：Kadane算法（推荐）

动态规划思想，遍历数组时维护当前子数组的最大和。

时间复杂度：O(n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
function maxSubArray(nums) {
    let maxCurrent = nums[0];
    let maxGlobal = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // 决定是继续当前子数组还是开始新的子数组
        maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
        // 更新全局最大值
        maxGlobal = Math.max(maxGlobal, maxCurrent);
    }
    
    return maxGlobal;
}

方法三：分治法

将数组分成左右两部分，分别求解，然后考虑跨越中间的子数组。

时间复杂度：O(n log n)
空间复杂度：O(log n)（递归栈空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function maxSubArray(nums) {
    return divideAndConquer(nums, 0, nums.length - 1);
}

function divideAndConquer(nums, left, right) {
    if (left === right) return nums[left];
    
    const mid = Math.floor((left + right) / 2);
    
    // 分别计算左半部分、右半部分和跨越中间的最大子数组和
    const leftMax = divideAndConquer(nums, left, mid);
    const rightMax = divideAndConquer(nums, mid + 1, right);
    const crossMax = maxCrossingSum(nums, left, mid, right);
    
    return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSum(nums, left, mid, right) {
    let leftSum = -Infinity;
    let sum = 0;
    for (let i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }
    
    let rightSum = -Infinity;
    sum = 0;
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }
    
    return leftSum + rightSum;
}

算法分析

  1. 暴力解法：简单直观，但效率低下，不适合大规模数据。
  2. Kadane算法：最优解，线性时间复杂度，空间复杂度为常数。
  3. 分治法：虽然时间复杂度不如Kadane算法，但展示了分治思想的应用。

实际应用

最大子数组和问题在金融分析中有广泛应用，例如：

  • 股票买卖时机分析
  • 基因组序列分析
  • 计算机视觉中的图像处理

变种问题

  1. 返回最大子数组本身而不仅仅是和
  2. 允许空子数组（最大和可以为0）
  3. 二维矩阵的最大子矩阵和

总结

对于最大子数组和问题，Kadane算法是最优解决方案，具有O(n)时间复杂度和O(1)空间复杂度。理解这个算法不仅有助于解决这个问题本身，还能帮助理解动态规划的基本思想。

最大子数组和问题详解（Kadane算法保姆级图解）

让我用最直观的方式为你解释Kadane算法，保证让你彻底明白！

情景模拟：你是一个股票投资人

假设你有一支股票连续几天的价格变化：

天数:   1   2   3   4   5   6   7   8   9
价格:  -2   1  -3   4  -1   2   1  -5   4

你需要在某一天买入，之后的某一天卖出，如何获得最大收益？

算法核心思想

我们维护两个变量：

  • current_sum：当前连续子数组的和
  • max_sum：迄今为止找到的最大和

第一步：初始化

current_sum = -2 (第一天必须买入)
max_sum = -2

第二步：逐日分析（关键！）

第2天（价格：1）

  • 选择1：从今天重新开始（只买今天）→ 和=1

  • 选择2：继续前一天的持仓（-2+1=-1）

  • 选择收益更高的方式：max(1, -1)=1

    current_sum = 1
    max_sum = max(-2, 1)=1

第3天（价格：-3）

  • 选择1：从今天重新开始 → 和=-3

  • 选择2：继续前一天的持仓（1-3=-2）

  • 选择：max(-3, -2)=-2

    current_sum = -2
    max_sum保持1不变

第4天（价格：4）

  • 选择1：从今天重新开始 → 和=4

  • 选择2：继续持仓（-2+4=2）

  • 选择：max(4, 2)=4

    current_sum = 4
    max_sum = max(1, 4)=4

第5天（价格：-1）

  • 选择1：重新开始 → -1

  • 选择2：继续持仓（4-1=3）

  • 选择：max(-1, 3)=3

    current_sum = 3
    max_sum保持4

第6天（价格：2）

  • 选择1：重新开始 → 2

  • 选择2：继续持仓（3+2=5）

  • 选择：max(2, 5)=5

    current_sum = 5
    max_sum = max(4, 5)=5

第7天（价格：1）

  • 选择1：重新开始 → 1

  • 选择2：继续持仓（5+1=6）

  • 选择：max(1, 6)=6

    current_sum = 6
    max_sum = max(5, 6)=6 ← 这就是我们要找的最大和！

第8天（价格：-5）

  • 选择1：重新开始 → -5

  • 选择2：继续持仓（6-5=1）

  • 选择：max(-5, 1)=1

    current_sum = 1
    max_sum保持6

第9天（价格：4）

  • 选择1：重新开始 → 4

  • 选择2：继续持仓（1+4=5）

  • 选择：max(4, 5)=5

    current_sum = 5
    max_sum保持6

最终结果

最大子数组和为6，对应的子数组是[4, -1, 2, 1]（第4-7天）

为什么这样有效？

  1. 贪心选择：每一步都做出局部最优选择
  2. 重启机制：当当前和变为负数时，后面的子数组不可能通过包含它变得更大
  3. 全局记录：始终记录遇到的最大值

代码再理解

1
2
3
4
5
6
7
8
9
10
11
12
13
function maxSubArray(nums) {
    let current_sum = nums[0];
    let max_sum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // 关键决策：是延续当前子数组，还是从当前元素重新开始？
        current_sum = Math.max(nums[i], current_sum + nums[i]);
        // 更新全局最大值
        max_sum = Math.max(max_sum, current_sum);
    }
    
    return max_sum;
}

常见误区

  1. 认为必须从正数开始 → 其实第一个元素可能是负数
  2. 认为遇到负数就要重启 → 只有当当前和变为负数时才需要
  3. 忽略单个元素的情况 → 最大子数组可能就是一个元素

现在你应该完全理解这个算法了吧？如果还有疑问，可以试着用这个思路手动计算另一个例子，比如[1, -2, 3, 5, -1, 2]。