LeetCode 热题 100——普通数组——最大子数组和

14.最大子数组和

题目描述

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

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

求解

（1）暴力
首先想到的基本都是暴力，该题的核心思路就是遍历所有的 nums[i…j]的和，保留最大值

1var maxSubArray = function(nums) {
2    // 暴力求解
3    let ans = -Infinity
4    // 穷举各种子数组nums[i...j]
5    for (let i = 0; i < nums.length; i++) {
6        for (let j = i; j < nums.length; j++) {
7            let sum = 0
8            for (let k = i; k <= j; k++) {
9                sum += nums[k]
10            }
11            ans = Math.max(ans, sum)
12        }
13    }
14    return ans
15};
16

有 10个用例超出时间限制
（2）暴力优化

1var maxSubArray = function(nums) {
2    // 暴力求解 —— 优化
3    let ans = -Infinity
4    for (let i = 0; i < nums.length; i++) {
5        let sum = 0
6        for (let j = i; j < nums.length; j++) {
7            // 内循环 每次都算出 i...i, i...n - 1 的值
8            sum += nums[j]
9            ans = Math.max(ans, sum)
10        }
11    }
12    return ans
13};
14

还是有六个超出了时间限制。。

（3）继续优化

本题主要使用动态规划，已经不记得动态规划是怎么回事了，先复习一波。。。
一、核心定义

动态规划是一种高效解决具有重叠子问题和最优子结构的复杂问题的算法思想。核心逻辑是：将大问题分解为若干个相互关联的小问题，通过求解小问题并缓存结果（避免重复计算），最终从子问题的解中构造出原问题的最优解。

二、两大核心前提（问题适用条件）

动态规划仅适用于满足以下两个条件的问题：

1. 重叠子问题（Overlapping Subproblems）
   大问题可分解为多个小问题，且这些小问题在求解过程中会被反复计算（而非相互独立）。
   示例：斐波那契数列中，fib(5) = fib(4) + fib(3)，而 fib(4) = fib(3) + fib(2)，fib(3) 被重复计算。
2. 最优子结构（Optimal Substructure）
   大问题的最优解可以由其子问题的最优解推导得出。
   即：若一个问题的最优解包含了子问题的解，那么这些子问题的解也必须是最优的。
   示例：从 A 到 C 的最短路径若经过 B，则 A→B 和 B→C 的路径也必须是各自的最短路径。

三、关键概念

1. 状态（State）
   对问题某一阶段的快照描述，通常用一个或一组变量表示（如 dp[i]、dp[i][j]）。
   作用：概括当前问题的进展，足以推导下一步状态。
   示例：dp[i] 可表示 “爬到第 i 阶楼梯的方法数”“以第 i 个元素结尾的最大子数组和”。
2. 状态转移方程（State Transition Equation）
   动态规划的核心灵魂，定义了 “如何从先前的状态计算当前状态”。
   形式：dp[i] = f(dp[i-1], dp[i-2], …)（由子问题的解推导当前解）。
   示例：爬楼梯中 dp[i] = dp[i-1] + dp[i-2]（从 i-1 阶爬 1 步，或从 i-2 阶爬 2 步）。
3. DP 表（DP Table）
   存储子问题解的数据结构（通常是数组或哈希表），用于缓存结果、避免重复计算。
   维度：根据状态定义确定（一维、二维或多维）。
   示例：一维 dp[] 解决爬楼梯、最大子数组和；二维 dp[i][j] 解决最长公共子序列（LCS）。
4. 初始化（Initialization）
   确定 DP 表的初始值（最小子问题的解），是状态转移的起点。
   示例：爬楼梯中 dp[1] = 1、dp[2] = 2；最大子数组和中 dp[0] = nums[0]。
5. 计算顺序（Order of Calculation）
   确定填充 DP 表的顺序，确保计算 dp[i] 时，所有依赖的子问题（如 dp[i-1]）已被求解。
   常见顺序：从左到右、从上到下（自底向上）。

四、解题步骤（通用流程）

• 定义状态：明确 dp[i] 或 dp[i][j] 的具体含义（最关键步骤）。
• 推导状态转移方程：找出当前状态与子状态的关系。
• 初始化 DP 表：设置最小子问题的初始值。
• 按顺序填充 DP 表：确保依赖的子状态已计算完成。
• 返回结果：从 DP 表中提取原问题的解（可能是 dp[n]、max(dp[]) 等）。

五、两种实现方式

1. 自底向上（Bottom-Up）- 迭代法
   思路：从最小子问题开始，逐步向上求解，直到解决原问题。
   实现：使用 DP 表（数组 / 哈希表）迭代填充。
   优点：无递归开销，效率高，无栈溢出风险。
   示例：爬楼梯、最大子数组和的迭代解法。
2. 自顶向下（Top-Down）- 递归 + 记忆化（Memoization）
   思路：从原问题出发，递归分解为子问题；用 “备忘录”（哈希表 / 数组）缓存已求解的子问题，避免重复计算。
   实现：递归函数 + 备忘录（如 memo 对象）。
   优点：逻辑直观，贴近问题的递归描述。
   缺点：存在递归调用开销，可能栈溢出（适用于子问题数量较少的场景）。
   示例（爬楼梯）：

1function climbStairs(n, memo = {}) {  
2	if (n in memo) return memo[n]; // 缓存命中，直接返回  
3	if (n === 1) return 1;  
4	if (n === 2) return 2;  
5	memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo); // 递归求解并缓存  
6	return memo[n];  
7}  

六、经典例题解析（DP 模型）

应用场景：
动态规划主要用于解决以下三类问题：
优化问题：求最大 / 最小、最长 / 最短（如最大子数组和、最短路径）。
计数问题：求方案数、组合数（如爬楼梯、不同路径）。
字符串问题：子序列、子串匹配（如 LCS、最长回文子串）。

• 最大子数组和思路：

定义状态 (DP State)：我们定义 dp[i] 表示以数组中第 i 个元素 结尾 的连续子数组的最大和。
例如，对于数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]：
dp[0] 表示以 -2 结尾的最大子数组和，它就是 -2 本身。
dp[1] 表示以 1 结尾的最大子数组和，它可以是 1 或者 -2 + 1，取最大值 1。
dp[2] 表示以 -3 结尾的最大子数组和，它可以是 -3 或者 1 + (-3)，取最大值 -2。
dp[3] 表示以 4 结尾的最大子数组和，它可以是 4 或者 -2 + 4，取最大值 4。
以此类推…
确定状态转移方程 (State Transition)：对于第 i 个元素，我们有两种选择：a. 只取第 i 个元素本身，作为一个新的子数组的起点。b. 将第 i 个元素加入到以第 i-1 个元素结尾的子数组中。
因此，状态转移方程为：dp[i] = max(nums[i], dp[i-1] + nums[i])
nums[i] 对应选择 a。
dp[i-1] + nums[i] 对应选择 b。
我们取两者中的较大值作为 dp[i] 的值。
初始化 (Initialization)：dp[0] = nums[0]，因为以第一个元素结尾的子数组只有它自己。
最终结果 (Result Extraction)：我们需要遍历整个 dp 数组，找到其中的最大值。这个最大值就是所有可能的连续子数组中的最大和。因为 dp[i] 只代表以 i 结尾的最大子数组和，整个数组的最大子数组可能在任意位置结束。
result = max(dp[0…n-1])

代码实现：

1var maxSubArray = function(nums) {
2    if (nums.length === 1) return nums[0]
3    // 动态规划 
4    let dp = new Array(nums.length)
5    dp[0] = nums[0]
6    let ans = -Infinity // 当nums长度为1的时候，不会进入循环，存在边界问题
7    // let ans = dp[0]
8    // dp[i]代表的是 截至当前位置i的子数组的 最大子数组和
9    // i位置需要考虑：i本身  i + (i - 1)之前的子数组和
10    for (let i = 1; i < nums.length; i++) {
11        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
12        ans = Math.max(ans, dp[i])
13    }
14    return ans
15};
16

可以一起进行判断：

1// 使用动态规划
2var maxSubArray = function(nums) {
3    // 动态规划 
4    let dp = new Array(nums.length)
5    dp[0] = nums[0]
6    ans = dp[0]
7    for (let i = 1; i < nums.length; i++) {
8        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
9        ans = Math.max(ans, dp[i])
10    }
11    return ans
12};
13

正好学习了动态规划，把 爬楼梯也做了

15. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：
1 <= n <= 45

求解

dp[i]：爬到第 i 阶楼梯的方法数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
初始化状态：dp[1] = 1，dp[2] = 2

代码：

1var climbStairs = function(n) {
2    if (n === 1) return 1
3    if (n === 2) return 2
4    let n1 = 1, n2 = 2
5    let ans = 0
6    for (let i = 3; i <= n; i++) {
7        ans = n1 + n2
8        n1 = n2
9        n2 = ans
10    }
11    return ans
12};
13

也可以使用递归

有点事情忙了好几天，断了断了，今天开始补。加油加油！

《LeetCode 热题 100——普通数组——最大子数组和》 是转载文章，点击查看原文。