最大子数组和（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]。

合并区间

问题描述

给定一个区间集合 intervals，其中 intervals[i] = [starti, endi]，合并所有重叠的区间，并返回一个不重叠的区间数组。

示例

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠，合并为 [1,6]

解决思路

方法：排序 + 合并

1. 排序：首先将所有区间按照起始点进行排序
2. 合并：然后遍历排序后的区间，逐个合并重叠的区间

算法步骤

1. 如果区间数量为0，直接返回空数组
2. 按区间的起始点进行排序
3. 初始化结果数组，放入第一个区间
4. 从第二个区间开始遍历：
   • 如果当前区间的起始点 <= 结果数组中最后一个区间的结束点（有重叠）
     • 合并这两个区间，更新结果数组最后一个区间的结束点为两者的较大值
   • 否则（无重叠）
     • 直接将当前区间加入结果数组

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function merge(intervals) {
    if (intervals.length === 0) return [];
    
    // 按起始点排序
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const last = merged[merged.length - 1];
        const current = intervals[i];
        
        if (current[0] <= last[1]) {
            // 有重叠，合并区间
            last[1] = Math.max(last[1], current[1]);
        } else {
            // 无重叠，直接添加
            merged.push(current);
        }
    }
    
    return merged;
}

示例解析

以输入 [[1,3],[2,6],[8,10],[15,18]] 为例：

1. 排序后（已有序）：[[1,3],[2,6],[8,10],[15,18]]
2. 初始化：merged = [[1,3]]
3. **处理 [2,6]**：
   • 比较 2 <= 3 → 有重叠
   • 合并为 [1, max(3,6)] = [1,6]
   • merged = [[1,6]]
4. **处理 [8,10]**：
   • 比较 8 <= 6 → 无重叠
   • 直接添加
   • merged = [[1,6],[8,10]]
5. **处理 [15,18]**：
   • 比较 15 <= 10 → 无重叠
   • 直接添加
   • merged = [[1,6],[8,10],[15,18]]
6. 最终结果：[[1,6],[8,10],[15,18]]

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(n)，存储结果需要额外空间

边界情况考虑

1. 空输入：直接返回空数组
2. 单区间输入：直接返回原数组
3. 完全重叠区间：如 [[1,4],[2,3]] 应合并为 [[1,4]]
4. 相邻区间：如 [[1,4],[4,5]] 应合并为 [[1,5]]

可视化示例

原始区间：
[1,3] [2,6] [8,10] [15,18]
  |----|
    |------|
           |----|
                 |-----|

合并过程：
1. [1,3] 和 [2,6] 重叠 → [1,6]
2. [1,6] 和 [8,10] 不重叠
3. [8,10] 和 [15,18] 不重叠

最终结果：
[1,6] [8,10] [15,18]
 |------|
         |----|
               |-----|

总结

合并区间问题的关键在于：

1. 先排序使区间有序
2. 逐个比较并合并重叠区间
3. 注意处理各种边界情况

这种方法高效且易于理解，适用于大多数区间合并场景。