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

Ne0inhk

— 19 min read
【动态规划】子数组、子串问题

一、最大子数组和

题目描述：

在这里插入图片描述

思路讲解：
本道题需要我们找到数组中连续子数组的最大和，子数组需连续且至少包含一个元素，问题可拆解为：以第 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 中存储的就是整个数组中最大的连续子数组和，直接返回即可

编写代码：

classSolution{public:intmaxSubArray(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)（普通最大子数组和与环形子数组和的最大值）

编写代码：

classSolution{public:intmaxSubarraySumCircular(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 中存储的就是整个数组中乘积最大的连续子数组的乘积，直接返回即可

编写代码：

classSolution{public:intmaxProduct(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 中存储的就是乘积为正数的最长子数组长度，直接返回即可

编写代码：

classSolution{public:intgetMaxLen(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;}elseif(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 数组后得到的总和，即为数组中所有等差数列子数组的总个数

编写代码：

classSolution{public:intnumberOfArithmeticSlices(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 中存储的就是最长湍流子数组的长度，直接返回即可

编写代码：

classSolution{public:intmaxTurbulenceSize(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 个字符）能否被拆分，返回该值即可

编写代码：

classSolution{public:boolwordBreak(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 结尾的独特子串数量）

编写代码：

classSolution{public:intfindSubstringInWraproundString(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;}};

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹

Read more

东方审美算法解构：Asian Beauty Z-Image Turbo如何通过提示词工程强化文化特征

东方审美算法解构：Asian Beauty Z-Image Turbo如何通过提示词工程强化文化特征 1. 项目简介与核心价值 Asian Beauty Z-Image Turbo是一款专门针对东方美学优化的本地图像生成工具，基于通义千问Tongyi-MAI Z-Image底座模型，注入经过充分训练的Asian-beauty专用权重（v1.0_20版本）。这个工具的核心价值在于：不需要联网就能生成符合东方审美的精致人像，所有数据处理都在本地完成，彻底保障隐私安全。 与通用图像生成模型不同，这个工具从底层就针对东方人像特征进行了专门优化。通过精心设计的提示词工程和模型参数调优，能够生成更加符合东方审美的高质量人像图片。无论是面部特征、肤色质感还是整体气质，都更加贴近真实的东方美感。 2. 技术架构与优化策略 2.1 模型架构设计 工具采用BF16精度加载模型，在保证生成质量的同时显著降低显存占用。通过权重注入方式部署Asian-beauty专用safetensors权重，这些权重经过大量东方人像数据的训练，能够更好地捕捉和表现东方美学特征。 技术架构的核心优势在于：

By Ne0inhk

MinHash 去重策略：小白也能轻松上手的大规模文本去重神器

MinHash 去重策略：小白也能轻松上手的大规模文本去重神器 大家好！今天我们来聊一个在大数据时代特别实用的技术——MinHash 去重策略。如果你刚接触数据处理、网页爬虫、AI 训练数据清洗等场景，经常会遇到一个头疼的问题：手里有成千上万甚至上亿篇文本，怎么快速找出重复或几乎一模一样的文章？ 直接一个个比对？太慢了！MinHash 就是专门为这种大规模“近似去重”而生的工具。它能快速判断两篇文本是否高度相似，而且速度快、内存省。下面我们用最通俗的语言，一步步带你搞懂它。 为什么需要近似去重？ * 完全重复：两篇文章一字不差，用普通哈希（如 MD5）就能轻松检测。 * 近似重复：有人改了几个词、加了广告、换了标题……内容 90% 一样，这时候普通哈希就失效了。 MinHash 的强项就是捕捉这种“近似重复”，特别适合新闻聚合、爬虫去重、AI 训练数据清洗等场景。 MinHash 的核心思路：把文本变成集合，

By Ne0inhk

《数据结构(C语言版)》严蔚敏_吴伟民 第三版 高清扫描版

《数据结构(C语言版)》严蔚敏_吴伟民 第三版 高清扫描版 【下载地址】数据结构C语言版严蔚敏_吴伟民第三版高清扫描版探索数据结构的核心精髓，开启编程世界的智慧之门！《数据结构(C语言版)》第三版高清扫描版，由严蔚敏与吴伟民联袂打造，权威且实用。高清画质确保每一页都清晰可见，完整内容涵盖所有章节与附录，让您深入理解数据结构的奥秘。无需携带厚重的实体书，随时随地通过电子设备畅享知识盛宴。无论是初学者还是进阶者，这份资源都将成为您学习数据结构的得力助手。立即下载，开启您的数据结构学习之旅，掌握编程的基石，迈向技术巅峰！ 项目地址: https://gitcode.com/Premium-Resources/2bed9 《数据结构(C语言版)》是由严蔚敏和吴伟民共同编写的大学教材，目前已更新至第三版。本书全面系统地介绍了数据结构的基础知识及其在C语言中的应用，内容丰富，结构清晰，是学习数据结构不可或缺的参考资料。 本仓库提供的是《数据结构(C语言版)》第三版的高清扫描版资源，具有以下特点： * 高清扫描，保证了文本的清晰度和可读性。 * 内容完整，包含了书籍的所有章节和附录。

By Ne0inhk