《LeetCode 152 乘积最大子数组 || LeetCode 413 等差数列划分》
一、题目
二、做题思路
2.1 状态表示（核心基础）
本题要求计算数组中乘积最大的连续子数组。由于负数相乘可能反转大小关系，仅记录最大乘积不够，还需记录最小乘积。因此定义两个状态：
f[i]表示以nums[i]结尾的子数组的最大乘积。g[i]表示以nums[i]结尾的子数组的最小乘积。
2.2 状态转移方程（关键难点）
对于以nums[i]结尾的子数组，有三种可能来源：
单独成为子数组：即
nums[i]自身。延续前一个最大乘积：
f[i-1] * nums[i]。延续前一个最小乘积：
g[i-1] * nums[i]（当nums[i]为负数时，乘以最小可能得最大）。
因此，当前最大和最小乘积分别为三者中的最大值和最小值：f[i] = max(nums[i], f[i-1]*nums[i], g[i-1]*nums[i])g[i] = min(nums[i], f[i-1]*nums[i], g[i-1]*nums[i])
2.3 初始化（边界防护）
第一个元素（下标 0）没有前驱，因此f[0] = g[0] = nums[0]，同时全局最大乘积ret初始化为nums[0]。
2.4 填表顺序（递推方向）
每个i状态仅依赖i-1的状态，因此必须从左到右（即i从 1 到n-1）依次填充两个数组，确保每个状态计算时，其所有前置状态均已就绪。
2.5 返回值（目标映射）
题目要求返回整个数组中乘积最大的连续子数组的乘积，即所有f[i]中的最大值。我们在递推过程中同步维护ret，最终返回ret。
三、代码
class Solution { public: int maxProduct(vector<int>& nums) { int n = nums.size(); // 边界处理：若数组为空，返回0（题目一般保证非空，但为健壮性加上） if (n == 0) return 0; // 1. 创建dp表 // f[i] : 以 nums[i] 结尾的子数组的最大乘积 // g[i] : 以 nums[i] 结尾的子数组的最小乘积 // 维护最小乘积是因为负数乘以负数可能变成正数，从而成为最大乘积 vector<int> f(n); vector<int> g(n); // 2. 初始化：第一个元素结尾的最大和最小乘积都是 nums[0] f[0] = g[0] = nums[0]; int ret = nums[0]; // 全局最大乘积 // 3. 填表顺序：从左到右（i 从 1 到 n-1），因为 f[i] 依赖 f[i-1] 和 g[i-1] for (int i = 1; i < n; i++) { int x = nums[i]; // 单独成为子数组 int y = f[i - 1] * nums[i]; // 乘以前一个最大乘积 int z = g[i - 1] * nums[i]; // 乘以前一个最小乘积 // 4. 状态转移方程： // 当前最大乘积 = max(单独, 最大乘当前, 最小乘当前) f[i] = max(x, max(y, z)); // 当前最小乘积 = min(单独, 最大乘当前, 最小乘当前) g[i] = min(x, min(y, z)); // 更新全局最大乘积 ret = max(ret, f[i]); } // 5. 返回值：全局最大乘积 return ret; } };四、流程图
五、题目
六、做题思路
6.1 状态表示（核心基础）
本题要求计算数组中所有等差数列子数组的个数。由于等差数列子数组必须是连续的，且长度至少为 3，我们定义dp[i]表示以nums[i]结尾的等差数列子数组的个数。
6.2 状态转移方程（关键难点）
要判断以nums[i]结尾能否形成新的等差数列，只需检查最后三个元素nums[i-2]、nums[i-1]、nums[i]是否构成等差，即nums[i] - nums[i-1] == nums[i-1] - nums[i-2]。
若满足，则以
nums[i]结尾的等差数列数 = 以nums[i-1]结尾的等差数列数 + 1（新增一个长度为 3 的子数组[nums[i-2], nums[i-1], nums[i]]，同时之前的所有等差数列向后延伸一位也形成新的更长的数列）。若不满足，则无法形成新的等差数列，
dp[i] = 0。
因此方程：dp[i] = (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) ? dp[i-1] + 1 : 0。
6.3 初始化（边界防护）
长度小于 3 的数组不可能构成等差数列，因此若n < 3，直接返回 0。对于dp[0]和dp[1]，它们无法作为长度≥3 的结尾，默认初始化为 0。
6.4 填表顺序（递推方向）
dp[i]仅依赖dp[i-1]和前两个元素，因此必须从左到右（即i从 2 到n-1）依次填充dp表，确保每个状态计算时，其前置状态已就绪。
6.5 返回值（目标映射）
题目要求返回所有等差数列子数组的总个数。每个子数组都有唯一的结尾位置，因此总数为所有dp[i]的累加和：total = sum(dp[i])（i从 2 到n-1）。我们在递推过程中累加dp[i]，最终返回total。
七、代码
class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size(); // 若数组长度小于3，不可能存在等差数列，直接返回0（题目保证n>=1，但为健壮性加上） if (n < 3) return 0; // 1. 创建dp表 // dp[i] 表示以 nums[i] 结尾的等差数列（长度≥3）的个数 // 例如 nums = [1,2,3,4]，dp[2]=1（[1,2,3]），dp[3]=2（[2,3,4]和[1,2,3,4]） vector<int> dp(n, 0); int total = 0; // 累计所有等差数列总数 // 2. 初始化：dp[0]和dp[1]默认为0，无需显式赋值 // 3. 填表顺序：从左到右（i从2到n-1），因为dp[i]依赖dp[i-1]和前两个元素 for (int i = 2; i < n; i++) { // 4. 状态转移方程： // 若当前三个连续元素构成等差数列（nums[i]-nums[i-1] == nums[i-1]-nums[i-2]）， // 则以i结尾的等差数列个数 = 以i-1结尾的个数 + 1（新增的以[i-2,i-1,i]为结尾的长度为3的数列） // 否则，无法形成新的等差数列，dp[i] = 0 dp[i] = (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) ? dp[i - 1] + 1 : 0; // 累加所有dp[i]即为总个数（因为每个等差数列都有唯一结尾位置） total += dp[i]; } // 5. 返回值：累计的等差数列总数 return total; } };