《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(vectorint nums) { int n nums.size(); // 边界处理若数组为空返回0题目一般保证非空但为健壮性加上 if (n 0) return 0; // 1. 创建dp表 // f[i] : 以 nums[i] 结尾的子数组的最大乘积 // g[i] : 以 nums[i] 结尾的子数组的最小乘积 // 维护最小乘积是因为负数乘以负数可能变成正数从而成为最大乘积 vectorint f(n); vectorint 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(vectorint nums) { int n nums.size(); // 若数组长度小于3不可能存在等差数列直接返回0题目保证n1但为健壮性加上 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] vectorint 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; } };八、流程图