动态规划之“最大子数组和”问题的三种算法

动态规划之“最大子数组和”问题的三种算法

一、关键概念

- 子数组：原数组中连续的一段元素。
- 子序列：元素顺序不变但不一定连续。
- 连续子序列：等价于子数组。

二、暴力算法

- 核心思路：枚举所有可能的连续子数组，计算和并记录最大值。
- 固定起点 i ，遍历所有终点 j （ j ≥ i ），累加 i 到 j 的和，与当前最大值比较并更新。
- 优缺点：
- 优点：逻辑简单，新手易理解。
- 缺点：时间复杂度为 O(n^2) ，数组长度大时会超时。
- 代码实现：通过两层循环实现，支持 C++、Python 等语言。

三、分治算法

- 核心思想：将大问题拆分为小问题，解决后合并结果。
- 把数组从中间分为左右两半，最大子数组只可能出现在左半部分、右半部分、跨越中间的部分这三处，分别求解这三处的最大值，最终取最大者。
- 左、右半部分的最大子数组可通过递归求解；跨越中间的部分需分别从中间向左、向右遍历累加，取左右最大和之和。
- 优缺点：
- 优点：时间复杂度优化为 O(n\log n) 。
- 缺点：递归逻辑较复杂，新手理解难度大，且递归有额外栈开销。

四、Kadane算法（动态规划解法）

- 状态定义： dp[i] 表示以第 i 个元素结尾的最大子数组和。
- 状态转移方程： dp[i] = max(dp[i-1] + a[i], a[i]) ，即要么将第 i 个元素加入前一个子数组，要么以第 i 个元素单独作为子数组。
- 优化：由于计算 dp[i] 仅需 dp[i-1] ，可通过变量 cur_max 记录前一个状态，空间复杂度优化为 O(1) 。
- 优缺点：
- 优点：实现简单、易理解，时间复杂度 O(n) ，空间复杂度可优化至 O(1) ，是面试常考的最优解法。
- 缺点：无明显缺点。

五、面试技巧

在算法面试中，即使知道最优算法，也可先讲暴力算法，再讲分治算法，最后讲 Kadane 算法，展现思考过程，让面试官觉得你是灵活思考而非死记硬背。