最大子数组和问题的分析思路

发表于 分类于 阅读次数：

问题描述

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

分析思路

1. 问题可视化

1
2
3
4
5
6
7
8
9
10
11
12
示例数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

可视化表示:
     ┌─┐
     │4│
     └─┘     ┌─┐
┌─┐   │    ┌─┐│2│┌─┐
│1│   │    │ ││ ││1│
└─┘   │    └─┘└─┘└─┘     ┌─┐
│     │     │     │      │4│
└─────┴─────┴─────┴──────└─┘
-2 1 -3  4  -1  2  1  -5  4

2. 思路分析

  1. 局部最优解：

    1
    2
    3
    4
    5
    6
    7
    8
    位置i的最大子数组和有两种可能：
    ┌────────────────┐
    │ 1. 加入前面的和 │
    └────────────────┘
             或
    ┌────────────┐
    │ 2. 从自己开始 │
    └────────────┘

  2. 状态转移：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    dp[i] = max(nums[i], dp[i-1] + nums[i])

    示意图：
    dp[i-1] < 0  →  ┌─────┐
                     │重新开始│
                     └─────┘

    dp[i-1] > 0  →  ┌─────┐
                     │继续累加│
                     └─────┘

3. 解题思路图解

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
数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

步骤分析:
1) -2: [-2]
   └── 当前最大和: -2

2) 1:  [-2, 1]
   └── 重新开始: 1

3) -3: [1, -3]
   └── 继续累加: -2，重新开始

4) 4:  [4]
   └── 重新开始: 4

5) -1: [4, -1]
   └── 继续累加: 3

6) 2:  [4, -1, 2]
   └── 继续累加: 5

7) 1:  [4, -1, 2, 1]
   └── 继续累加: 6

8) -5: [4, -1, 2, 1, -5]
   └── 继续累加: 1

9) 4:  [4, -1, 2, 1, -5, 4]
   └── 继续累加: 5

4. 关键观察

  1. 连续性质：

    1
    2
    [a] → [a,b] → [a,b,c]
         连续扩展

  2. 决策点：

    1
    2
    3
    4
    5
    6
    7
    当前位置i的决策:
    ┌─────────────┐
    │ 加入前面的和 │ ← dp[i-1] > 0
    └─────────────┘
    ┌─────────┐
    │ 重新开始 │ ← dp[i-1] ≤ 0
    └─────────┘

5. 优化思路

  1. 空间优化：

    1
    2
    3
    4
    只需要记录:
    ┌──────────┐    ┌──────────┐
    │当前最大和│ 和 │全局最大和│
    └──────────┘    └──────────┘

  2. 时间优化：

    1
    2
    3
    一次遍历 → O(n)
    无需回溯
    无需额外空间

总结

  1. 问题的核心是理解：在每个位置，我们要决定是加入之前的和，还是重新开始。

  2. 使用动态规划思想，但可以优化为O(1)空间复杂度。

  3. 关键是理解局部最优和全局最优的关系。