【动态规划】子数组、子串问题

题目描述：

思路讲解：
本道题需要我们找到数组中连续子数组的最大和，子数组需连续且至少包含一个元素，问题可拆解为：以第 i 个元素结尾的最大子数组和，要么是将第 i 个元素加入前一个子数组，要么是从第 i 个元素重新开始。以下是具体思路：

1. 状态表示：dp[i] 表示以第 i 个元素为结尾的连续子数组的最大和
2. 状态转移方程：
   • dp[i] = max(dp[i-1] + nums[i], nums[i])
     • 若 dp[i-1] + nums[i] 更大，说明以第 i-1 个元素结尾的子数组可以延续到第 i 个元素，形成更长的子数组
     • 若 nums[i] 更大，说明从第 i 个元素重新开始的子数组和更大，放弃之前的子数组
3. 初始化：
   • 第 0 个元素：dp[0] = nums[0]，即以第 0 个元素为结尾的子数组最大和就是其自身
4. 填写 DP 表与结果保存：
   • 按照从左到右的顺序，从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），基于前一个位置的 dp 值计算当前值
   • 同时维护一个变量 ret，实时记录遍历过程中出现的最大 dp 值（即所有以不同位置为结尾的子数组和的最大值）
5. 结果返回：
   • 遍历结束后，ret 中存储的就是整个数组中最大的连续子数组和，直接返回即可

编写代码：

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n,0);dp[0] = nums[0];int ret = dp[0];for(int i = 1 ; i < n ; i++){dp[i] = max(dp[i-1] + nums[i],nums[i]);ret = max(ret,dp[i]);}return ret;}
};

题目描述：

思路讲解：
本道题需要我们计算环形子数组的最大和，数组呈环形，最大子数组可能是：

• 普通的非环形子数组（不跨首尾）
  • 问题可拆解为：以第 i 个元素结尾的最大子数组和，要么是将第 i 个元素加入前一个子数组，要么是从第 i 个元素重新开始
• 环形子数组（包含首尾元素，中间跳过一段最小和的子数组）
  • 问题可拆解为：以第 i 个元素结尾的最小子数组和，要么是将第 i 个元素加入前一个子数组，要么是从第 i 个元素重新开始，最后通过整个数组的和 - 最小数组和，得到最大数组和

通过计算两种情况的最大值，即可得到环形子数组的最大和。以下是具体思路：

1. 状态表示：
   • f[i] 表示以第 i 个元素为结尾的最大连续子数组和（非环形场景）
   • g[i] 表示以第 i 个元素为结尾的最小连续子数组和（用于计算环形场景）
2. 状态转移方程：
   • f[i] = max(nums[i], f[i-1] + nums[i])
     • 以 i 结尾的最大子数组，要么从 i 重新开始，要么延续 i-1 的最大子数组
   • g[i] = min(nums[i], g[i-1] + nums[i])
     • 以 i 结尾的最小子数组，要么从 i 重新开始，要么延续 i-1 的最小子数组
3. 初始化：
   • 第 0 个元素：f[0] = nums[0]，即以第 0 个元素为结尾的子数组最大和就是其自身
   • 第 0 个元素：g[0] = nums[0]，即以第 0 个元素为结尾的子数组最小和就是其自身
4. 填写 DP 表：
   • 按照从左到右的顺序，从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），基于前一个位置的 f，g 值计算当前值
   • 维护一个变量 fmax，实时记录遍历过程中出现的最大 f 值
   • 维护一个变量 gmin，实时记录遍历过程中出现的最小 g 值
   • 维护一个变量 sum，实时记录整个数组的和
5. 结果返回：
   • 若数组所有元素均为负数（sum == gmin，即最小子数组和等于总和），此时环形子数组会包含所有元素（和为负数），应返回非环形的最大子数组和 fmax
   • 否则，返回 max(fmax, sum - gmin)（普通最大子数组和与环形子数组和的最大值）

编写代码：

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> f(n,0) , g(n,0);f[0] = g[0] = nums[0];int sum = nums[0];int fmax = f[0] , gmin = g[0];for(int i = 1 ; i < n ; i++){f[i] = max(nums[i],f[i-1] + nums[i]);g[i] = min(nums[i],g[i-1] + nums[i]);fmax = max(fmax,f[i]);gmin = min(gmin,g[i]);sum += nums[i];}return sum == gmin ? fmax : max(fmax,sum - gmin);}
};

题目描述：

思路讲解：
本道题需要我们计算出数组中非空连续子数组的最大乘积，乘积最大子数组与最大子数组和的区别在于：负负相乘可能得正，因此需同时跟踪最大和最小乘积。以下是具体思路：

1. 状态表示：
   • f[i] 表示以第 i 个元素为结尾的连续子数组的最大乘积
   • g[i] 表示以第 i 个元素为结尾的连续子数组的最小乘积
2. 状态转移方程：
   • f[i] = max(nums[i], max(f[i-1] * nums[i], g[i-1] * nums[i]))
     • 以 i 结尾的最大乘积，可能是：当前元素本身、前一个最大乘积乘以当前元素、前一个最小乘积乘以当前元素（负负得正的情况），取三者最大值
   • g[i] = min(nums[i], min(g[i-1] * nums[i], f[i-1] * nums[i]))
     • 以 i 结尾的最小乘积，可能是：当前元素本身、前一个最小乘积乘以当前元素、前一个最大乘积乘以当前元素（正负得负的情况），取三者最小值
3. 初始化：
   • 第 0 个元素：f[0] = g[0] = nums[0]，即以第 0 个元素为结尾的子数组，最大和最小乘积均为其自身
4. 填写 DP 表与结果保存：
   • 按照从左到右的顺序，从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），基于前一个位置的 f 和 g 值计算当前值
   • 同时维护变量 ret，实时记录遍历过程中出现的最大 f[i]（即所有以不同位置为结尾的子数组的最大乘积）
5. 结果返回：
   • 遍历结束后，ret 中存储的就是整个数组中乘积最大的连续子数组的乘积，直接返回即可

编写代码：

class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> f(n,0) , g(n,0);f[0] = g[0] = nums[0];int ret = f[0];for(int i = 1 ; i < n ; i++){f[i] = max(nums[i],max(f[i-1] * nums[i],g[i-1] * nums[i]));g[i] = min(nums[i],min(g[i-1] * nums[i],f[i-1] * nums[i]));ret = max(ret,f[i]);}return ret;}
};

题目描述：

思路讲解：
本道题需要我们找出数组中乘积为正数的最长子数组的长度，乘积为正数的子数组需满足：元素乘积为正（负数个数为偶数，且无 0），需要区分两种状态跟踪子数组长度。以下是具体思路：

1. 状态表示：
   • f[i] 表示以第 i 个元素为结尾的乘积为正数的最长子数组长度
   • g[i] 表示以第 i 个元素为结尾的乘积为负数的最长子数组长度
2. 状态转移方程：
   • 根据当前元素 nums[i] 的值分三种情况：
     • 当前元素为 0：
       • 子数组包含 0 时乘积为 0，故 f[i] = 0，g[i] = 0（无法形成正 / 负乘积子数组）
     • 当前元素为正数：
       • 正乘积子数组可延续前一个正乘积子数组（正数 × 正数仍为正）：f[i] = f[i-1] + 1
       • 负乘积子数组需延续前一个负乘积子数组（负数 × 正数仍为负），若前无负乘积子数组则为 0：g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1
     • 当前元素为负数：
       • 正乘积子数组需延续前一个负乘积子数组（负数 × 负数为正），若前无负乘积子数组则为 0：f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1
       • 负乘积子数组可延续前一个正乘积子数组（正数 × 负数为负）：g[i] = f[i-1] + 1
3. 初始化：
   • 第 0 个元素：
     • 若 nums[0] > 0：f[0] = 1（自身形成正乘积子数组），g[0] = 0（无负乘积子数组）
     • 若 nums[0] < 0：f[0] = 0（无正乘积子数组），g[0] = 1（自身形成负乘积子数组）
     • 若 nums[0] = 0：f[0] = g[0] = 0
4. 填写 DP 表与结果保存：
   • 按照从左到右的顺序，从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），基于前一个位置的 f 和 g 值计算当前值
   • 维护变量 ret，实时记录遍历过程中出现的最大 f[i]（即最长正乘积子数组长度）
5. 结果返回：
   • 遍历结束后，ret 中存储的就是乘积为正数的最长子数组长度，直接返回即可

编写代码：

class Solution {
public:int getMaxLen(vector<int>& nums) {int n = nums.size();vector<int> f(n,0) , g(n,0);f[0] = nums[0] > 0 ? 1 : 0;g[0] = nums[0] < 0 ? 1 : 0;int ret = f[0];for(int i = 1 ; i < n ; i++){if(nums[i] == 0){f[i] = 0;g[i] = 0;}else if(nums[i] > 0){f[i] = f[i-1] + 1;g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;}else{f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;g[i] = f[i-1] + 1; }ret = max(ret,f[i]);}return ret;}
};

题目描述：

思路讲解：
本道题需要我们找出数组中子数组为等差数列的个数，等差数列子数组需满足：长度至少为 3，且任意相邻元素差相等，问题可拆解为：若当前位置与前两个位置构成等差数列，则以当前位置为结尾的新等差数列子数组个数 = 以前一个位置为结尾的个数 + 1。以下是具体思路：

1. 状态表示：dp[i] 表示以第 i 个元素为结尾的等差数列子数组的个数
2. 状态转移方程：
   • 若 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]（即三个连续元素构成等差数列），则 dp[i] = dp[i-1] + 1
   • 否则，dp[i] = 0（当前位置无法构成以其为结尾的等差数列子数组）
   • 当第 i 个元素能与前两个元素形成等差数列时，会新增一个包含 i 的子数组，同时继承之前所有以 i-1 为结尾的子数组（将 i 加入后仍为等差数列）
3. 初始化：
   • 数组长度小于 3 时，不存在等差数列子数组，返回 0
   • dp[0] = dp[1] = 0：前两个元素无法构成长度 >= 3 的子数组，故初始化为 0
4. 填写 DP 表：
   • 按照从左到右的顺序，从第 2 个元素遍历到最后一个元素（i=2 到 i=n-1），判断是否构成等差数列并更新 dp[i]
5. 结果返回：
   • 累加 dp 数组后得到的总和，即为数组中所有等差数列子数组的总个数

编写代码：

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();vector<int> dp(n,0);for(int i = 2 ; i < n ; i++){if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2])dp[i] = dp[i-1] + 1;}int ret = 0;for(int i = 0 ; i < n ; i++){ret += dp[i];}return ret;}
};

题目描述：

思路讲解：
本道题需要我们找出最长湍流子数组的长度，湍流子数组要求相邻元素的比较符号交替翻转（如 <,>,< 或 >,<,>），所以我们需要定义两个状态数组分别记录两种交替模式下以每个位置为结尾的最长湍流子数组长度。以下是具体思路：

1. 状态表示：
   • f[i] 表示以第 i 个位置为结尾中所有子数组，最后呈现为“上升”趋势的最长湍流子数组的长度
   • g[i] 表示以第 i 个位置为结尾中所有子数组，最后呈现为“下降”趋势的最长湍流子数组的长度
2. 状态转移方程：
   • 若 arr[i] > arr[i-1]（当前为上升）：
     • 前一个比较必须为下降才能形成交替，故 f[i] = g[i-1] + 1（延续前一个下降模式并加 1）
   • 若 arr[i] < arr[i-1]（当前为下降）：
     • 前一个比较必须为上升才能形成交替，故 g[i] = f[i-1] + 1（延续前一个上升模式并加 1）
   • 若 arr[i] == arr[i-1]：
     • 无法形成湍流（比较符号不翻转），故 f[i] = g[i] = 1（重置为 1，仅含当前元素）
3. 初始化：
   • 所有位置初始值为 1：f[i] = g[i] = 1（单个元素本身是长度为 1 的湍流子数组）
4. 填写 DP 表与结果保存：
   • 采用自底向上顺序，从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），根据相邻元素的大小关系更新 f[i] 和 g[i]
   • 维护变量 ret，实时记录遍历过程中 f[i] 和 g[i] 的最大值（即最长湍流子数组长度）
5. 结果返回：
   • 遍历结束后，ret 中存储的就是最长湍流子数组的长度，直接返回即可

编写代码：

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();vector<int> f(n,1) , g(n,1);int ret = f[0];for(int i = 1 ; i < n ; i++){if(arr[i] > arr[i-1]) f[i] = g[i-1] + 1;if(arr[i] < arr[i-1]) g[i] = f[i-1] + 1;ret = max(ret,f[i]);ret = max(ret,g[i]);}return ret;}
};

题目描述：

思路讲解：
本道题需要我们判断字符串 s 能否被拆分为字典 wordDict 中的单词组合，可重复使用字单词，问题可拆解为：前 i 个字符能否拆分，取决于是否存在某个 j < i，使得前 j 个字符可拆分且 j 到 i 的子串在字典中。以下是具体思路：

1. 状态表示：dp[i] 表示字符串 s 的前 i 个字符（即 s [0…i-1]）能否被字典中的单词拼接而成（true表示可以，false表示不可以）
2. 状态转移方程：
   • 对于 i ≥ 1（前 i 个字符）：
     • 若存在 j（1 ≤ j ≤ i），使得：
       • dp[j-1] 为 true（前 j-1 个字符可拆分）
       • 子串 s[j-1…i-1]（即从第 j 个字符到第 i 个字符）存在于字典中
       • 则 dp[i] = true（前 i 个字符可拆分）
3. 初始化：
   • dp[0] = true：空字符串可被拆分（作为拆分的起点）
   • 为方便截取子串，将原字符串 s 前加一个空格得到news，使下标从 1 开始对应原字符串的第 0 个字符
4. 填写 DP 表与字典优化：
   • 按照从左到右的顺序，外层循环遍历前 i 个字符（i=1 到 i=n），内层循环遍历可能的拆分点 j（1 ≤ j ≤ i）
   • 将字典转为哈希集合hash，实现 O (1) 时间复杂度的单词存在性判断
5. 结果返回：
   • 最终 dp[n] 表示整个字符串 s（前 n 个字符）能否被拆分，返回该值即可

编写代码：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();unordered_set<string> hash(wordDict.begin(),wordDict.end());vector<bool> dp(n + 1,false);dp[0] = true;string news = " " + s;for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= i ; j++){string sub = news.substr(j,i-j+1);if(dp[j-1] && hash.count(sub)) {dp[i] = true;}}}return dp[n];}
};

题目描述：

思路讲解：
本道题需要我们统计s中有多少不同非空子串也在 base 中出现，base 是 “abcdefghijklmnopqrstuvwxyz” 的无限循环，因此其中的子串需满足：每个相邻字符是连续的（如 “abc”），或 ‘z’ 后接 ‘a’（如 “zab”），以某个字符结尾的符合条件的子串，其最长长度决定了该字符贡献的独特子串数量。以下是本道题的具体思路：

1. 状态定义：
   • dp[i] 表示以 s 中第 i 个字符为结尾的最长连续符合 base 规则的子串长度（连续指符合 base 的字符顺序）
2. 状态转移方程：
   • 若当前字符与前一个字符符合 base 的连续规则（s[i] - s[i-1] == 1 或 s[i-1] == 'z’且s[i] == ‘a’），则 dp[i] = dp[i-1] + 1（延续前一个字符的连续子串）
   • 否则，dp[i] = 1（当前字符自身形成长度为 1 的子串）
3. 初始化：
   • dp数组长度为s的长度n，所有元素初始化为1
     • 单个字符自身是长度为 1 的符合条件的子串（如s[0]本身一定在base中）
   • 辅助数组arr长度为 26（对应 26 个小写字母），初始化为0，用于记录每个字符结尾的最长符合条件子串长度
4. 填写 DP 表：
   • 按照从左到右的顺序，遍历s从第 1 个字符到最后一个字符（i = 1到i = n-1），根据字符关系更新dp[i]
5. 去重统计：
   • 由于不同位置的相同字符可能贡献重复子串（如 “aba” 中两个 ‘a’ 的子串有重叠），需按字符去重：
   • 遍历dp数组，更新arr：arr[s[i]-‘a’] = max(arr[s[i]-‘a’], dp[i])
6. 结果计算：
   • 所有字符贡献的子串数量之和即为答案，即累加arr数组的所有元素（每个arr[c]的值等于以 c 结尾的独特子串数量）

编写代码：

class Solution {
public:int findSubstringInWraproundString(string s) {int n = s.size();vector<int> dp(n,1);for(int i = 1 ; i < n ; i++){if(s[i] - s[i-1] == 1 || (s[i-1] == 'z' && s[i] == 'a')) {dp[i] += dp[i-1];}}vector<int> arr(26,0);for(int i = 0 ; i < n ; i++){arr[s[i]-'a'] = max(arr[s[i]-'a'],dp[i]);}int ret = 0;for(int i = 0 ; i < 26 ; i++){ret += arr[i];}return ret;}
};