网站导航
> 技术文档 > 算法导论（动态规划）——子数组系列

算法导论（动态规划）——子数组系列

网友: 技术文档 2025-07-30 13:26:54

算法思路（53）

  1. 状态表示：
    在处理线性动态规划问题时，可以通过“经验 + 题目要求”来定义状态表示：

    • 以某个位置为结尾的情况；
    • 以某个位置为起点的情况。

    在本题中，我们选择更常用的方式，定义状态表示为：

    • dp[i] 表示以位置 i 为结尾的所有子数组中的最大和。

  2. 状态转移方程：
    为了计算 dp[i]，我们需要考虑两种情况：

    • 子数组长度为 1：此时 dp[i]=nums[i]。
    • 子数组长度大于 1：此时 dp[i] 应该等于以位置 i−1 结尾的所有子数组的最大和再加上当前元素 nums[i]，即 dp[i−1]+nums[i]。

    综合考虑这两种情况，由于我们需要得到最大值，因此可以得到状态转移方程：

    dp[i]=max⁡(nums[i],dp[i−1]+nums[i])

  3. 初始化：
    由于状态转移涉及到之前的状态，为了方便初始化，我们可以在最前面添加一个“辅助节点”：

    • 该节点的值应保证可以正确初始化后续状态，通常设为 0。
    • 在本题中，可以让 dp[0]=0 以表示没有元素的初始状态。

  4. 填表顺序：
    根据状态转移方程的定义，填表顺序应为“从左往右”，即先计算前面的状态再计算当前状态。

  5. 返回值：
    状态表表示的是以各个位置为结尾的所有子数组的最大和，但最大子数组和的具体结尾位置并不确定。因此，我们需要返回整个 dpdp 表中的最大值，这可以通过如下方式实现：

    结果=max⁡(dp)

C++:

class Solution {public: int maxSubArray(vector& nums) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n = nums.size(); vector dp(n + 1); int ret = INT_MIN; for(int i = 1; i <= n; i++) { dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]); ret = max(ret, dp[i]); } return ret; }};

Java：

class Solution { public int maxSubArray(int[] nums) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n = nums.length; int[] dp = new int[n + 1]; int ret = Integer.MIN_VALUE; for(int i = 1; i <= n; i++) { dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]); ret = Math.max(ret, dp[i]); } return ret; }}

算法思路（918）

这个问题要求我们寻找数组的最大子数组和，考虑数组的首尾相连的情况。因此总体思路分为两部分：

  1. 内部子数组和（Non-Circular Case）

    • 计算在数组内部的最大子数组和，记作 fmaxfmax​。

  2. 首尾相连的子数组和（Circular Case）

    • 如果结果在数组的首尾相连部分，那么我们可以认为数组中间有一部分是最小的子数组和。
    • 设总和为 sum，那么与中间部分对应的最大子数组和为 sum−gmin​，其中 gmin​ 表示数组的最小子数组和。

注意：两种情况下的最大值就是我们所需的结果。当数组全部为负数时，我们需要特殊判断，以确保最后返回的值正确。

具体步骤

  1. 状态表示：

    • 定义 g[i] 表示以元素 i 作为结尾的所有子数组和的最小值。

  2. 状态转移方程：

    • 对于 g[i] 的计算，可以分为两种情况：
      • 如果子数组长度为 1：g[i]=nums[i]
      • 如果子数组长度大于 1：g[i]=min⁡(g[i−1]+nums[i],nums[i])
    • 综上可以得到状态转移方程：g[i]=min⁡(nums[i],g[i−1]+nums[i])

  3. 初始化：

    • 为了方便计算，可以在数组前添加一个辅助节点，使得初始值为 0，即 g[0]=0。

  4. 填表顺序：

    • 按照状态转移方程自左向右填充状态数组。

  5. 返回值：

    • 计算完成后，首先找出 fmax（最大子数组和）。
    • 然后找出 gmin​（最小子数组和）。
    • 统计所有元素的总和 sum。
    • 最后根据条件返回相应的最大值：返回值=(sum==gmin)?fmax:max⁡(fmax,sum−gmin)

算法思路（152）

这道题旨在找到数组中连续子数组的最大乘积。与「最大子数组和」问题类似，我们需要考虑正负数对乘积的影响。由于负数可能会导致乘积变为正，我们不仅需要追踪最大乘积，还需要追踪最小乘积。以下是更清晰的算法思路。

具体步骤

  1. 状态表示：

    • f[i]：以索引 i 为结尾的所有子数组的最大乘积。
    • g[i]：以索引 i 为结尾的所有子数组的最小乘积。

  2. 状态转移方程：

    • 对于最大乘积 f[i]，我们有以下几种情况：

      • 子数组长度为 1： f[i]=nums[i]
      • 子数组长度大于 1，且 nums[i]>0 ：最大乘积可以通过前一个索引处的最大乘积计算得到： f[i]=max⁡(nums[i],f[i−1]×nums[i])
      • 子数组长度大于 1，且 nums[i]<0 ：最大乘积可能来自于前一个索引处的最小乘积： f[i]=max⁡(nums[i],g[i−1]×nums[i])

    • 对于最小乘积 g[i]g[i]，我们也需要考虑几种情况：

      • 子数组长度为 1： g[i]=nums[i]
      • 子数组长度大于 1，且 nums[i]>0 ：最小乘积可以通过前一个索引处的最小乘积计算得到： g[i]=min⁡(nums[i],g[i−1]×nums[i])
      • 子数组长度大于 1，且 nums[i]<0 ：最小乘积可能来自于前一个索引处的最大乘积： g[i]=min⁡(nums[i],f[i−1]×nums[i])

  3. 初始化：

    • 可以在数组前加上一个辅助节点来帮助初始化，设置 f[0]=g[0]=1（因为我们只在后续累乘时关心乘积，1 是乘法单位）。

  4. 填表顺序：

    • 根据状态转移方程，填表的顺序为“从左往右”。同时更新 f 和 g。

  5. 返回值：

    • 最后，返回 f 数组中的最大值，即数组的最大乘积。

C++:

class Solution {public: int maxProduct(vector& nums) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n = nums.size(); vector f(n + 1), g(n + 1); f[0] = g[0] = 1; int ret = INT_MIN; for(int i = 1; i <= n; i++) { int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1]; f[i] = max(x, max(y, z)); g[i] = min(x, min(y, z)); ret = max(ret, f[i]); } return ret; }};

Java：

class Solution { public int maxProduct(int[] nums) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回值 int n = nums.length; int[] f = new int[n + 1]; int[] g = new int[n + 1]; f[0] = g[0] = 1; int ret = Integer.MIN_VALUE; for(int i = 1; i <= n; i++) { int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1]; f[i] = Math.max(x, Math.max(y, z)); g[i] = Math.min(x, Math.min(y, z)); ret = Math.max(ret, f[i]); } return ret; }}

算法思路（413）

  1. 状态表示：

    • 我们定义状态 dp[i] 表示以 i 位置的元素为结尾的等差数列的数量。这样一来，我们关注的是每个元素作为等差数列的结尾，便于进行状态转移。

  2. 状态转移方程：

    • 为了判断三个数能否构成等差数列，我们可以利用等差数列的性质。如果三个数 nums[i−2],nums[i−1],nums[i] 可以形成等差数列，则它们满足以下条件：nums[i−2]+nums[i]=2⋅nums[i−1]
    • 根据这个条件，我们可以得出状态转移方程：
      • 如果 nums[i−2]+nums[i]≠2⋅nums[i−1]，那么 dp[i]=0。
      • 如果 nums[i−2]+nums[i]=2⋅nums[i−1]，那么 dp[i]=dp[i−1]+1，其中 dp[i−1] 表示以 i−1 为结尾的等差数列的数量，额外加上 1 是因为这三者也构成一个新的等差数列。

  3. 初始化：

    • 对于小于两个元素的情况，无法形成等差数列，因此需要初始化为 dp[0]=dp[1]=0（当数组长度小于 2 时，这种情况也是合理的）。

  4. 填表顺序：

    • 明确这一点后，我们可以从左到右逐步填充 dp 数组。

  5. 返回值：

    • 最后的结果是 dp 数组中所有元素的和，因为我们要求的是所有以不同元素结尾的等差数列的数量。

C++:

class Solution {public: int numberOfArithmeticSlices(vector& nums) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n = nums.size(); vector dp(n); int sum = 0; for(int i = 2; i < n; i++) { dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0; sum += dp[i]; } return sum; }};

Java：

class Solution { public int numberOfArithmeticSlices(int[] nums) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回值 int n = nums.length; int[] dp = new int[n]; int sum = 0; for(int i = 2; i < n; i++) { dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0; sum += dp[i]; } return sum; }}
网络标签：

相关问题