子数组、子串系列（典型算法思想）—— OJ例题算法解析思路

一、53. 最大子数组和 - 力扣（LeetCode）

算法代码： 

class Solution {
public:int maxSubArray(vector<int>& nums) {// 1. 创建 dp 表// dp[i] 表示以第 i 个元素结尾的子数组的最大和int n = nums.size();vector<int> dp(n + 1); // 定义大小为 n+1 的 dp 表// 2. 初始化int ret = INT_MIN; // 用于记录全局最大值，初始化为最小整数值// 3. 填表for (int i = 1; i <= n; i++) {// 状态转移方程：// dp[i] = max(单独作为子数组, 加入前面的子数组)dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);// 更新全局最大值ret = max(ret, dp[i]);}// 4. 返回结果return ret; // 返回全局最大值}
};

代码思路

1. 问题分析：

   • 目标是找到数组中连续子数组的最大和。

   • 使用动态规划来解决，定义dp[i]表示以第i个元素结尾的子数组的最大和。

2. 状态定义：

   • dp[i]：以第i个元素结尾的子数组的最大和。

3. 状态转移方程：

   • 对于第i个元素，有两种选择：

     • 单独作为一个子数组：nums[i-1]。

     • 加入前面的子数组：dp[i-1] + nums[i-1]。

   • 取两者的最大值：dp[i] = max(nums[i-1], dp[i-1] + nums[i-1])。

4. 初始化：

   • dp[0]没有意义，可以忽略。

   • dp[1]表示以第1个元素结尾的子数组的最大和，即nums[0]。

5. 结果：

   • 遍历dp表，找到最大值。

---

代码逻辑详解

1. 创建 DP 表：

   • int n = nums.size();

     • 获取数组的长度n。

   • vector<int> dp(n + 1);

     • 定义一个大小为n+1的数组dp，用于存储以每个位置结尾的子数组的最大和。

2. 初始化：

   • int ret = INT_MIN;

     • 初始化ret为最小整数值，用于记录全局最大值。

3. 填表：

   • for (int i = 1; i <= n; i++)

     • 遍历数组的每个元素，i表示当前元素的位置（从1开始）。

   • dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);

     • 计算以第i个元素结尾的子数组的最大和：

       • nums[i-1]：单独作为子数组。

       • dp[i-1] + nums[i-1]：加入前面的子数组。

     • 取两者的最大值。

   • ret = max(ret, dp[i]);

     • 更新全局最大值ret。

4. 返回结果：

   • return ret;

     • 返回全局最大值。

---

示例

假设输入数组为：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

执行过程：

1. 初始化：

   • dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   • ret = INT_MIN

2. 填表：

   • i=1：dp[1] = max(-2, 0 + -2) = -2，ret = max(INT_MIN, -2) = -2

   • i=2：dp[2] = max(1, -2 + 1) = 1，ret = max(-2, 1) = 1

   • i=3：dp[3] = max(-3, 1 + -3) = -2，ret = max(1, -2) = 1

   • i=4：dp[4] = max(4, -2 + 4) = 4，ret = max(1, 4) = 4

   • i=5：dp[5] = max(-1, 4 + -1) = 3，ret = max(4, 3) = 4

   • i=6：dp[6] = max(2, 3 + 2) = 5，ret = max(4, 5) = 5

   • i=7：dp[7] = max(1, 5 + 1) = 6，ret = max(5, 6) = 6

   • i=8：dp[8] = max(-5, 6 + -5) = 1，ret = max(6, 1) = 6

   • i=9：dp[9] = max(4, 1 + 4) = 5，ret = max(6, 5) = 6

3. 返回结果：6

---

总结

• 问题本质：动态规划解决最大子数组和问题。

• 核心思想：通过状态转移方程计算以每个位置结尾的子数组的最大和，并记录全局最大值。

• 时间复杂度：O(n)，遍历数组一次。

• 空间复杂度：O(n)，使用了一个大小为n+1的dp表。可以通过滚动变量优化为O(1)。

二、918. 环形子数组的最大和 - 力扣（LeetCode） 

算法代码：

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {// 1. 创建 dp 表// f[i] 表示以第 i 个元素结尾的最大子数组和// g[i] 表示以第 i 个元素结尾的最小子数组和int n = nums.size();vector<int> f(n + 1), g(n + 1); // 定义大小为 n+1 的 f 和 g 表// 2. 初始化int fmax = INT_MIN; // 记录全局最大子数组和int gmin = INT_MAX; // 记录全局最小子数组和int sum = 0; // 记录数组的总和// 3. 填表for (int i = 1; i <= n; i++) {int x = nums[i - 1]; // 当前元素// 计算以第 i 个元素结尾的最大子数组和f[i] = max(x, x + f[i - 1]);fmax = max(fmax, f[i]); // 更新全局最大子数组和// 计算以第 i 个元素结尾的最小子数组和g[i] = min(x, x + g[i - 1]);gmin = min(gmin, g[i]); // 更新全局最小子数组和sum += x; // 累加数组的总和}// 4. 返回结果// 如果数组所有元素为负数，则直接返回 fmax// 否则，返回 max(fmax, sum - gmin)return sum == gmin ? fmax : max(fmax, sum - gmin);}
};

代码思路

1. 问题分析：

   • 目标是找到环形数组中的最大子数组和。

   • 环形数组的特点是子数组可以跨越数组的末尾和开头。

   • 通过动态规划解决，分为两种情况：

     • 最大子数组不跨越数组边界（普通最大子数组和）。

     • 最大子数组跨越数组边界（总和减去最小子数组和）。

2. 状态定义：

   • f[i]：以第i个元素结尾的最大子数组和。

   • g[i]：以第i个元素结尾的最小子数组和。

3. 状态转移方程：

   • f[i] = max(nums[i-1], f[i-1] + nums[i-1])。

   • g[i] = min(nums[i-1], g[i-1] + nums[i-1])。

     

4. 初始化：

   • f[0]和g[0]没有意义，可以忽略。

   • fmax记录全局最大子数组和，gmin记录全局最小子数组和。

5. 结果：

   • 如果数组所有元素为负数，则直接返回fmax。

   • 否则，返回max(fmax, sum - gmin)，其中sum是数组的总和。

     

---

代码逻辑详解

1. 创建 DP 表：

   • int n = nums.size();

     • 获取数组的长度n。

   • vector<int> f(n + 1), g(n + 1);

     • 定义两个大小为n+1的数组f和g，分别用于存储最大子数组和和最小子数组和。

2. 初始化：

   • int fmax = INT_MIN;

     • 初始化fmax为最小整数值，用于记录全局最大子数组和。

   • int gmin = INT_MAX;

     • 初始化gmin为最大整数值，用于记录全局最小子数组和。

   • int sum = 0;

     • 初始化sum为0，用于记录数组的总和。

3. 填表：

   • for (int i = 1; i <= n; i++)

     • 遍历数组的每个元素，i表示当前元素的位置（从1开始）。

   • int x = nums[i - 1];

     • 获取当前元素x。

   • f[i] = max(x, x + f[i - 1]);

     • 计算以第i个元素结尾的最大子数组和：

       • x：单独作为子数组。

       • x + f[i-1]：加入前面的子数组。

     • 取两者的最大值。

   • fmax = max(fmax, f[i]);

     • 更新全局最大子数组和fmax。

   • g[i] = min(x, x + g[i - 1]);

     • 计算以第i个元素结尾的最小子数组和：

       • x：单独作为子数组。

       • x + g[i-1]：加入前面的子数组。

     • 取两者的最小值。

   • gmin = min(gmin, g[i]);

     • 更新全局最小子数组和gmin。

   • sum += x;

     • 累加数组的总和。

4. 返回结果：

   • return sum == gmin ? fmax : max(fmax, sum - gmin);

     • 如果数组所有元素为负数（sum == gmin），则直接返回fmax。

     • 否则，返回max(fmax, sum - gmin)，即最大子数组和或跨越边界的情况。

---

示例

假设输入数组为：nums = [5, -3, 5]

执行过程：

1. 初始化：

   • f = [0, 0, 0, 0]

   • g = [0, 0, 0, 0]

   • fmax = INT_MIN

   • gmin = INT_MAX

   • sum = 0

2. 填表：

   • i=1：

     • x = 5

     • f[1] = max(5, 5 + 0) = 5，fmax = max(INT_MIN, 5) = 5

     • g[1] = min(5, 5 + 0) = 5，gmin = min(INT_MAX, 5) = 5

     • sum = 5

   • i=2：

     • x = -3

     • f[2] = max(-3, -3 + 5) = 2，fmax = max(5, 2) = 5

     • g[2] = min(-3, -3 + 5) = -3，gmin = min(5, -3) = -3

     • sum = 2

   • i=3：

     • x = 5

     • f[3] = max(5, 5 + 2) = 7，fmax = max(5, 7) = 7

     • g[3] = min(5, 5 + -3) = 2，gmin = min(-3, 2) = -3

     • sum = 7

3. 返回结果：

   • sum == gmin为false，返回max(7, 7 - (-3)) = max(7, 10) = 10。

---

总结

• 问题本质：动态规划解决环形数组的最大子数组和问题。

• 核心思想：

  • 通过f[i]计算不跨越边界的最大子数组和。

  • 通过g[i]计算最小子数组和，用于处理跨越边界的情况。

• 时间复杂度：O(n)，遍历数组一次。

• 空间复杂度：O(n)，使用了两个大小为n+1的数组。可以通过滚动变量优化为O(1)。

三、152. 乘积最大子数组 - 力扣（LeetCode） 

算法代码： 

class Solution {
public:int maxProduct(vector<int>& nums) {// 1. 创建 dp 表// f[i] 表示以第 i 个元素结尾的子数组的最大乘积// g[i] 表示以第 i 个元素结尾的子数组的最小乘积int n = nums.size();vector<int> f(n + 1), g(n + 1); // 定义大小为 n+1 的 f 和 g 表// 2. 初始化f[0] = g[0] = 1; // 空数组的乘积为1int ret = INT_MIN; // 记录全局最大乘积// 3. 填表for (int i = 1; i <= n; i++) {int x = nums[i - 1]; // 当前元素int y = f[i - 1] * nums[i - 1]; // 当前元素与前面最大乘积的乘积int z = g[i - 1] * nums[i - 1]; // 当前元素与前面最小乘积的乘积// 计算以第 i 个元素结尾的最大乘积f[i] = max(x, max(y, z));// 计算以第 i 个元素结尾的最小乘积g[i] = min(x, min(y, z));// 更新全局最大乘积ret = max(ret, f[i]);}// 4. 返回结果return ret; // 返回全局最大乘积}
};

代码思路

1. 问题分析：

   • 目标是找到数组中连续子数组的最大乘积。

   • 由于乘积可能为正或负，需要同时记录以每个位置结尾的最大乘积和最小乘积。

2. 状态定义：

   • f[i]：以第i个元素结尾的子数组的最大乘积。

   • g[i]：以第i个元素结尾的子数组的最小乘积。

3. 状态转移方程：

   • 对于第i个元素，有三种选择：

     • 单独作为一个子数组：nums[i-1]。

     • 加入前面的最大乘积子数组：f[i-1] * nums[i-1]。

     • 加入前面的最小乘积子数组：g[i-1] * nums[i-1]。

   • 取三者的最大值和最小值：

     • f[i] = max(nums[i-1], f[i-1] * nums[i-1], g[i-1] * nums[i-1])。

     • g[i] = min(nums[i-1], f[i-1] * nums[i-1], g[i-1] * nums[i-1])。

4. 初始化：

   • f[0]和g[0]初始化为1，表示空数组的乘积为1（不影响后续计算）。

5. 结果：

   • 遍历f表，找到最大值。

     

---

代码逻辑详解

1. 创建 DP 表：

   • int n = nums.size();

     • 获取数组的长度n。

   • vector<int> f(n + 1), g(n + 1);

     • 定义两个大小为n+1的数组f和g，分别用于存储最大乘积和最小乘积。

2. 初始化：

   • f[0] = g[0] = 1;

     • 初始化f[0]和g[0]为1，表示空数组的乘积为1（不影响后续计算）。

   • int ret = INT_MIN;

     • 初始化ret为最小整数值，用于记录全局最大乘积。

3. 填表：

   • for (int i = 1; i <= n; i++)

     • 遍历数组的每个元素，i表示当前元素的位置（从1开始）。

   • int x = nums[i - 1];

     • 获取当前元素x。

   • int y = f[i - 1] * nums[i - 1];

     • 计算当前元素与前面最大乘积的乘积。

   • int z = g[i - 1] * nums[i - 1];

     • 计算当前元素与前面最小乘积的乘积。

   • f[i] = max(x, max(y, z));

     • 计算以第i个元素结尾的最大乘积：

       • x：单独作为子数组。

       • y：加入前面的最大乘积子数组。

       • z：加入前面的最小乘积子数组。

     • 取三者的最大值。

   • g[i] = min(x, min(y, z));

     • 计算以第i个元素结尾的最小乘积：

       • x：单独作为子数组。

       • y：加入前面的最大乘积子数组。

       • z：加入前面的最小乘积子数组。

     • 取三者的最小值。

   • ret = max(ret, f[i]);

     • 更新全局最大乘积ret。

4. 返回结果：

   • return ret;

     • 返回全局最大乘积。

---

示例

假设输入数组为：nums = [2, 3, -2, 4]

执行过程：

1. 初始化：

   • f = [1, 0, 0, 0, 0]

   • g = [1, 0, 0, 0, 0]

   • ret = INT_MIN

2. 填表：

   • i=1：

     • x = 2

     • y = 1 * 2 = 2

     • z = 1 * 2 = 2

     • f[1] = max(2, max(2, 2)) = 2

     • g[1] = min(2, min(2, 2)) = 2

     • ret = max(INT_MIN, 2) = 2

   • i=2：

     • x = 3

     • y = 2 * 3 = 6

     • z = 2 * 3 = 6

     • f[2] = max(3, max(6, 6)) = 6

     • g[2] = min(3, min(6, 6)) = 3

     • ret = max(2, 6) = 6

   • i=3：

     • x = -2

     • y = 6 * -2 = -12

     • z = 3 * -2 = -6

     • f[3] = max(-2, max(-12, -6)) = -2

     • g[3] = min(-2, min(-12, -6)) = -12

     • ret = max(6, -2) = 6

   • i=4：

     • x = 4

     • y = -2 * 4 = -8

     • z = -12 * 4 = -48

     • f[4] = max(4, max(-8, -48)) = 4

     • g[4] = min(4, min(-8, -48)) = -48

     • ret = max(6, 4) = 6

3. 返回结果：6

---

总结

• 问题本质：动态规划解决最大子数组乘积问题。

• 核心思想：

  • 通过f[i]记录以第i个元素结尾的最大乘积。

  • 通过g[i]记录以第i个元素结尾的最小乘积，用于处理负数情况。

• 时间复杂度：O(n)，遍历数组一次。

• 空间复杂度：O(n)，使用了两个大小为n+1的数组。可以通过滚动变量优化为O(1)。

四、1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode） 

算法代码： 

class Solution {
public:int getMaxLen(vector<int>& nums) {// 1. 创建 dp 表// f[i] 表示以第 i 个元素结尾的乘积为正数的子数组的最大长度// g[i] 表示以第 i 个元素结尾的乘积为负数的子数组的最大长度int n = nums.size();vector<int> f(n + 1), g(n + 1); // 定义大小为 n+1 的 f 和 g 表// 2. 初始化int ret = 0; // 记录全局最大长度// 3. 填表for (int i = 1; i <= n; i++) {if (nums[i - 1] > 0) { // 当前元素为正数f[i] = f[i - 1] + 1; // 正数乘以正数仍为正数g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; // 正数乘以负数为负数} else if (nums[i - 1] < 0) { // 当前元素为负数f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; // 负数乘以负数为正数g[i] = f[i - 1] + 1; // 负数乘以正数为负数} else { // 当前元素为0f[i] = 0; // 乘积为0，无法形成正数的子数组g[i] = 0; // 乘积为0，无法形成负数的子数组}ret = max(ret, f[i]); // 更新全局最大长度}// 4. 返回结果return ret; // 返回全局最大长度}
};

代码思路

1. 问题分析：

   • 目标是找到数组中乘积为正数的连续子数组的最大长度。

   • 由于乘积的正负性取决于负数的个数，需要同时记录以每个位置结尾的乘积为正数和负数的子数组的最大长度。

2. 状态定义：

   • f[i]：以第i个元素结尾的乘积为正数的子数组的最大长度。

   • g[i]：以第i个元素结尾的乘积为负数的子数组的最大长度。

3. 状态转移方程：

   • 如果当前元素为正数：

     • f[i] = f[i-1] + 1（正数乘以正数仍为正数）。

     • g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1（正数乘以负数为负数）。

   • 如果当前元素为负数：

     • f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1（负数乘以负数为正数）。

     • g[i] = f[i-1] + 1（负数乘以正数为负数）。

   • 如果当前元素为0：

     • f[i] = 0，g[i] = 0（乘积为0，无法形成正数或负数的子数组）。

4. 初始化：

   • f[0]和g[0]初始化为0，表示空数组的长度为0。

5. 结果：

   • 遍历f表，找到最大值。

     

---

代码逻辑详解

1. 创建 DP 表：

   • int n = nums.size();

     • 获取数组的长度n。

   • vector<int> f(n + 1), g(n + 1);

     • 定义两个大小为n+1的数组f和g，分别用于存储乘积为正数和负数的子数组的最大长度。

2. 初始化：

   • int ret = 0;

     • 初始化ret为0，用于记录全局最大长度。

3. 填表：

   • for (int i = 1; i <= n; i++)

     • 遍历数组的每个元素，i表示当前元素的位置（从1开始）。

   • if (nums[i - 1] > 0)

     • 如果当前元素为正数：

       • f[i] = f[i - 1] + 1;

         • 正数乘以正数仍为正数，长度加1。

       • g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;

         • 正数乘以负数为负数，如果前面没有负数的子数组，则长度为0。

   • else if (nums[i - 1] < 0)

     • 如果当前元素为负数：

       • f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;

         • 负数乘以负数为正数，如果前面没有负数的子数组，则长度为0。

       • g[i] = f[i - 1] + 1;

         • 负数乘以正数为负数，长度加1。

   • else

     • 如果当前元素为0：

       • f[i] = 0;

         • 乘积为0，无法形成正数的子数组。

       • g[i] = 0;

         • 乘积为0，无法形成负数的子数组。

   • ret = max(ret, f[i]);

     • 更新全局最大长度ret。

4. 返回结果：

   • return ret;

     • 返回全局最大长度。

---

示例

假设输入数组为：nums = [1, -2, -3, 4]

执行过程：

1. 初始化：

   • f = [0, 0, 0, 0, 0]

   • g = [0, 0, 0, 0, 0]

   • ret = 0

2. 填表：

   • i=1：

     • nums[0] = 1（正数）

     • f[1] = f[0] + 1 = 1

     • g[1] = g[0] == 0 ? 0 : g[0] + 1 = 0

     • ret = max(0, 1) = 1

   • i=2：

     • nums[1] = -2（负数）

     • f[2] = g[1] == 0 ? 0 : g[1] + 1 = 0

     • g[2] = f[1] + 1 = 2

     • ret = max(1, 0) = 1

   • i=3：

     • nums[2] = -3（负数）

     • f[3] = g[2] == 0 ? 0 : g[2] + 1 = 3

     • g[3] = f[2] + 1 = 1

     • ret = max(1, 3) = 3

   • i=4：

     • nums[3] = 4（正数）

     • f[4] = f[3] + 1 = 4

     • g[4] = g[3] == 0 ? 0 : g[3] + 1 = 0

     • ret = max(3, 4) = 4

3. 返回结果：4

---

总结

• 问题本质：动态规划解决乘积为正数的子数组的最大长度问题。

• 核心思想：

  • 通过f[i]记录以第i个元素结尾的乘积为正数的子数组的最大长度。

  • 通过g[i]记录以第i个元素结尾的乘积为负数的子数组的最大长度。

• 时间复杂度：O(n)，遍历数组一次。

• 空间复杂度：O(n)，使用了两个大小为n+1的数组。可以通过滚动变量优化为O(1)。

五、413. 等差数列划分 - 力扣（LeetCode） 

算法代码：

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {// 1. 创建 dp 表// dp[i] 表示以第 i 个元素结尾的等差数列的个数int n = nums.size();vector<int> dp(n); // 定义大小为 n 的 dp 表// 2. 初始化int sum = 0; // 用于累加所有等差数列的个数// 3. 填表for (int i = 2; i < n; i++) {// 检查当前元素是否可以加入前面的等差数列if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {// 如果可以加入，则等差数列的个数加1dp[i] = dp[i - 1] + 1;} else {// 如果不能加入，则等差数列的个数为0dp[i] = 0;}// 累加当前等差数列的个数sum += dp[i];}// 4. 返回结果return sum; // 返回等差数列的总数}
};

代码思路

1. 问题分析：

   • 目标是找到数组中等差数列的个数。

   • 等差数列的定义是：至少包含3个元素，且相邻元素的差值相等。

2. 状态定义：

   • dp[i]：以第i个元素结尾的等差数列的个数。

3. 状态转移方程：

   • 如果nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，则当前元素可以加入前面的等差数列，形成新的等差数列。

     • dp[i] = dp[i-1] + 1。

   • 否则，当前元素不能加入前面的等差数列，dp[i] = 0。

4. 初始化：

   • dp[0]和dp[1]初始化为0，因为至少需要3个元素才能形成等差数列。

5. 结果：

   • 遍历dp表，累加所有dp[i]的值，得到等差数列的总数。

---

代码逻辑详解

1. 创建 DP 表：

   • int n = nums.size();

     • 获取数组的长度n。

   • vector<int> dp(n);

     • 定义一个大小为n的数组dp，用于存储以每个位置结尾的等差数列的个数。

2. 初始化：

   • int sum = 0;

     • 初始化sum为0，用于累加所有等差数列的个数。

3. 填表：

   • for (int i = 2; i < n; i++)

     • 遍历数组的每个元素，i表示当前元素的位置（从2开始，因为至少需要3个元素才能形成等差数列）。

   • if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])

     • 检查当前元素是否可以加入前面的等差数列：

       • 如果nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，则当前元素可以加入前面的等差数列。

   • dp[i] = dp[i - 1] + 1;

     • 如果可以加入，则等差数列的个数加1。

   • else dp[i] = 0;

     • 如果不能加入，则等差数列的个数为0。

   • sum += dp[i];

     • 累加当前等差数列的个数。

4. 返回结果：

   • return sum;

     • 返回等差数列的总数。

---

示例

假设输入数组为：nums = [1, 2, 3, 4]

执行过程：

1. 初始化：

   • dp = [0, 0, 0, 0]

   • sum = 0

2. 填表：

   • i=2：

     • nums[2] - nums[1] = 1，nums[1] - nums[0] = 1。

     • dp[2] = dp[1] + 1 = 1。

     • sum = 0 + 1 = 1。

   • i=3：

     • nums[3] - nums[2] = 1，nums[2] - nums[1] = 1。

     • dp[3] = dp[2] + 1 = 2。

     • sum = 1 + 2 = 3。

3. 返回结果：3

---

总结

• 问题本质：动态规划解决等差数列的个数问题。

• 核心思想：

  • 通过dp[i]记录以第i个元素结尾的等差数列的个数。

  • 如果当前元素可以加入前面的等差数列，则dp[i] = dp[i-1] + 1，否则dp[i] = 0。

• 时间复杂度：O(n)，遍历数组一次。

• 空间复杂度：O(n)，使用了一个大小为n的数组。可以通过滚动变量优化为O(1)。

六、978. 最长湍流子数组 - 力扣（LeetCode）

算法代码： 

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {// 1. 创建 dp 表// f[i] 表示以第 i 个元素结尾且最后两个元素是上升趋势的湍流子数组的最大长度// g[i] 表示以第 i 个元素结尾且最后两个元素是下降趋势的湍流子数组的最大长度int n = arr.size();vector<int> f(n, 1), g(n, 1); // 定义大小为 n 的 f 和 g 表，初始化为1// 2. 初始化int ret = 1; // 记录全局最大长度，初始化为1（至少有一个元素）// 3. 填表for (int i = 1; i < n; i++) {if (arr[i - 1] < arr[i]) { // 当前元素比前一个元素大f[i] = g[i - 1] + 1; // 上升趋势，更新 f[i]} else if (arr[i - 1] > arr[i]) { // 当前元素比前一个元素小g[i] = f[i - 1] + 1; // 下降趋势，更新 g[i]}// 如果 arr[i-1] == arr[i]，则 f[i] 和 g[i] 保持为1ret = max(ret, max(f[i], g[i])); // 更新全局最大长度}// 4. 返回结果return ret; // 返回全局最大长度}
};

代码思路

1. 问题分析：

   • 目标是找到数组中最长的湍流子数组的长度。

   • 湍流子数组的定义是：相邻元素的差值符号交替变化（即大小关系交替变化）。

2. 状态定义：

   • f[i]：以第i个元素结尾且最后两个元素是上升趋势（arr[i-1] < arr[i]）的湍流子数组的最大长度。

   • g[i]：以第i个元素结尾且最后两个元素是下降趋势（arr[i-1] > arr[i]）的湍流子数组的最大长度。

3. 状态转移方程：

   • 如果arr[i-1] < arr[i]，则当前元素可以加入前面的下降趋势子数组，形成新的上升趋势子数组：

     • f[i] = g[i-1] + 1。

   • 如果arr[i-1] > arr[i]，则当前元素可以加入前面的上升趋势子数组，形成新的下降趋势子数组：

     • g[i] = f[i-1] + 1。

   • 如果arr[i-1] == arr[i]，则当前元素无法加入前面的湍流子数组，f[i] = 1，g[i] = 1。

4. 初始化：

   • f[i]和g[i]初始化为1，表示每个元素本身可以作为一个长度为1的湍流子数组。

5. 结果：

   • 遍历f和g表，找到最大值。

---

代码逻辑详解

1. 创建 DP 表：

   • int n = arr.size();

     • 获取数组的长度n。

   • vector<int> f(n, 1), g(n, 1);

     • 定义两个大小为n的数组f和g，初始化为1，表示每个元素本身可以作为一个长度为1的湍流子数组。

2. 初始化：

   • int ret = 1;

     • 初始化ret为1，表示至少有一个元素。

3. 填表：

   • for (int i = 1; i < n; i++)

     • 遍历数组的每个元素，i表示当前元素的位置（从1开始）。

   • if (arr[i - 1] < arr[i])

     • 如果当前元素比前一个元素大：

       • f[i] = g[i - 1] + 1;

         • 当前元素可以加入前面的下降趋势子数组，形成新的上升趋势子数组。

   • else if (arr[i - 1] > arr[i])

     • 如果当前元素比前一个元素小：

       • g[i] = f[i - 1] + 1;

         • 当前元素可以加入前面的上升趋势子数组，形成新的下降趋势子数组。

   • ret = max(ret, max(f[i], g[i]));

     • 更新全局最大长度ret。

4. 返回结果：

   • return ret;

     • 返回全局最大长度。

---

示例

假设输入数组为：arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]

执行过程：

1. 初始化：

   • f = [1, 1, 1, 1, 1, 1, 1, 1, 1]

   • g = [1, 1, 1, 1, 1, 1, 1, 1, 1]

   • ret = 1

2. 填表：

   • i=1：

     • arr[0] = 9，arr[1] = 4（下降）

     • g[1] = f[0] + 1 = 2

     • ret = max(1, 2) = 2

   • i=2：

     • arr[1] = 4，arr[2] = 2（下降）

     • g[2] = f[1] + 1 = 2

     • ret = max(2, 2) = 2

   • i=3：

     • arr[2] = 2，arr[3] = 10（上升）

     • f[3] = g[2] + 1 = 3

     • ret = max(2, 3) = 3

   • i=4：

     • arr[3] = 10，arr[4] = 7（下降）

     • g[4] = f[3] + 1 = 4

     • ret = max(3, 4) = 4

   • i=5：

     • arr[4] = 7，arr[5] = 8（上升）

     • f[5] = g[4] + 1 = 5

     • ret = max(4, 5) = 5

   • i=6：

     • arr[5] = 8，arr[6] = 8（相等）

     • f[6] = 1，g[6] = 1

     • ret = max(5, 1) = 5

   • i=7：

     • arr[6] = 8，arr[7] = 1（下降）

     • g[7] = f[6] + 1 = 2

     • ret = max(5, 2) = 5

   • i=8：

     • arr[7] = 1，arr[8] = 9（上升）

     • f[8] = g[7] + 1 = 3

     • ret = max(5, 3) = 5

3. 返回结果：5

---

总结

• 问题本质：动态规划解决最长湍流子数组问题。

• 核心思想：

  • 通过f[i]记录以第i个元素结尾且最后两个元素是上升趋势的湍流子数组的最大长度。

  • 通过g[i]记录以第i个元素结尾且最后两个元素是下降趋势的湍流子数组的最大长度。

• 时间复杂度：O(n)，遍历数组一次。

• 空间复杂度：O(n)，使用了两个大小为n的数组。可以通过滚动变量优化为O(1)。

 

七、139. 单词拆分 - 力扣（LeetCode）

算法代码： 

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {// 优化⼀：将字典⾥的单词存在哈希表⾥unordered_set<string> hash;for (auto& s : wordDict)hash.insert(s); // 将字典中的单词插入哈希表int n = s.size(); // 获取字符串的长度vector<bool> dp(n + 1); // 定义大小为 n+1 的 dp 表dp[0] = true; // 初始化 dp[0] 为 true，表示空字符串可以被拼接s = ' ' + s; // 在字符串前添加一个空格，使下标从 1 开始// 填 dp[i]for (int i = 1; i <= n; i++) {// 枚举最后一个单词的起始位置 jfor (int j = i; j >= 1; j--) {// 如果 dp[j-1] 为 true，且 s[j..i] 在字典中if (dp[j - 1] && hash.count(s.substr(j, i - j + 1))) {dp[i] = true; // 更新 dp[i] 为 truebreak; // 优化⼆：找到满足条件的 j 后立即跳出循环}}}// 返回 dp[n]，表示整个字符串是否可以被拼接return dp[n];}
};

代码思路

1. 问题分析：

   • 目标是判断字符串s是否可以由字典wordDict中的单词拼接而成。

   • 使用动态规划解决，定义dp[i]表示字符串s的前i个字符是否可以被字典中的单词拼接。

2. 状态定义：

   • dp[i]：字符串s的前i个字符是否可以被字典中的单词拼接。

3. 状态转移方程：

   • 对于每个位置i，枚举最后一个单词的起始位置j（从i到1）：

     • 如果dp[j-1]为true，且s[j..i]在字典中，则dp[i] = true。

   • 如果找不到满足条件的j，则dp[i] = false。

4. 初始化：

   • dp[0] = true，表示空字符串可以被拼接（即不选任何单词）。

5. 优化：

   • 将字典中的单词存储在哈希表中，方便快速查找。

   • 在找到满足条件的j后，立即跳出内层循环（优化二）。

---

代码逻辑详解

1. 优化一：哈希表存储字典：

   • unordered_set<string> hash;

     • 定义一个哈希表hash，用于存储字典中的单词。

   • for (auto& s : wordDict) hash.insert(s);

     • 将字典中的单词插入哈希表，方便快速查找。

2. 初始化 DP 表：

   • int n = s.size();

     • 获取字符串s的长度n。

   • vector<bool> dp(n + 1);

     • 定义一个大小为n+1的布尔数组dp，用于存储状态。

   • dp[0] = true;

     • 初始化dp[0]为true，表示空字符串可以被拼接。

3. 调整字符串下标：

   • s = ' ' + s;

     • 在字符串s前添加一个空格，使字符串的下标从1开始，方便后续处理。

4. 填表：

   • for (int i = 1; i <= n; i++)

     • 遍历字符串的每个位置，i表示当前字符的位置（从1开始）。

   • for (int j = i; j >= 1; j--)

     • 枚举最后一个单词的起始位置j（从i到1）。

   • if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))

     • 如果dp[j-1]为true，且s[j..i]在字典中：

       • dp[j-1]表示前j-1个字符可以被拼接。

       • s.substr(j, i - j + 1)表示从j到i的子串。

       • hash.count(...)检查子串是否在字典中。

   • dp[i] = true;

     • 如果满足条件，则dp[i]为true。

   • break;

     • 找到满足条件的j后，立即跳出内层循环（优化二）。

5. 返回结果：

   • return dp[n];

     • 返回dp[n]，表示整个字符串是否可以被拼接。

---

示例

假设输入：

• s = "leetcode"

• wordDict = ["leet", "code"]

执行过程：

1. 初始化：

   • hash = {"leet", "code"}

   • dp = [true, false, false, false, false, false, false, false, false]

   • s = " leetcode"

2. 填表：

   • i=1：

     • j=1：s[1..1] = "l"不在字典中。

     • dp[1] = false。

   • i=2：

     • j=2：s[2..2] = "e"不在字典中。

     • j=1：s[1..2] = "le"不在字典中。

     • dp[2] = false。

   • i=3：

     • j=3：s[3..3] = "e"不在字典中。

     • j=2：s[2..3] = "ee"不在字典中。

     • j=1：s[1..3] = "lee"不在字典中。

     • dp[3] = false。

   • i=4：

     • j=4：s[4..4] = "t"不在字典中。

     • j=3：s[3..4] = "et"不在字典中。

     • j=2：s[2..4] = "eet"不在字典中。

     • j=1：s[1..4] = "leet"在字典中。

     • dp[4] = true。

   • i=5：

     • j=5：s[5..5] = "c"不在字典中。

     • j=4：s[4..5] = "tc"不在字典中。

     • j=3：s[3..5] = "etc"不在字典中。

     • j=2：s[2..5] = "eetc"不在字典中。

     • j=1：s[1..5] = "leetc"不在字典中。

     • dp[5] = false。

   • i=6：

     • j=6：s[6..6] = "o"不在字典中。

     • j=5：s[5..6] = "co"不在字典中。

     • j=4：s[4..6] = "tco"不在字典中。

     • j=3：s[3..6] = "etco"不在字典中。

     • j=2：s[2..6] = "eetco"不在字典中。

     • j=1：s[1..6] = "leetco"不在字典中。

     • dp[6] = false。

   • i=7：

     • j=7：s[7..7] = "d"不在字典中。

     • j=6：s[6..7] = "od"不在字典中。

     • j=5：s[5..7] = "cod"不在字典中。

     • j=4：s[4..7] = "tcod"不在字典中。

     • j=3：s[3..7] = "etcod"不在字典中。

     • j=2：s[2..7] = "eetcod"不在字典中。

     • j=1：s[1..7] = "leetcod"不在字典中。

     • dp[7] = false。

   • i=8：

     • j=8：s[8..8] = "e"不在字典中。

     • j=7：s[7..8] = "de"不在字典中。

     • j=6：s[6..8] = "ode"不在字典中。

     • j=5：s[5..8] = "code"在字典中。

     • dp[8] = true。

3. 返回结果：true

---

总结

• 问题本质：动态规划解决字符串是否可以由字典中的单词拼接而成。

• 核心思想：

  • 通过dp[i]记录前i个字符是否可以被拼接。

  • 枚举最后一个单词的起始位置j，检查dp[j-1]和s[j..i]是否满足条件。

• 时间复杂度：O(n^2)，外层循环n次，内层循环最多n次。

• 空间复杂度：O(n)，使用了一个大小为n+1的dp表和一个哈希表。

八、467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode） 

算法代码： 

class Solution {
public:int findSubstringInWraproundString(string s) {int n = s.size(); // 获取字符串的长度// 1. 利用 dp 求出每个位置结尾的最长连续子数组的长度vector<int> dp(n, 1); // 定义大小为 n 的 dp 表，初始化为1for (int i = 1; i < n; i++) {// 检查当前字符是否是前一个字符的下一个字母if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a')) {dp[i] = dp[i - 1] + 1; // 如果是，则长度加1}}// 2. 计算每一个字符结尾的最长连续子数组的长度int hash[26] = {0}; // 定义哈希表，记录以每个字母结尾的最长环绕子串的长度for (int i = 0; i < n; i++) {// 更新以当前字符结尾的最长环绕子串的长度hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);}// 3. 将结果累加起来int sum = 0; // 定义累加结果for (auto x : hash) {sum += x; // 累加哈希表中的值}return sum; // 返回最终结果}
};

代码思路

1. 问题分析：

   • 目标是找到字符串s中所有唯一的环绕子串的数量。

   • 环绕子串的定义是：子串中的字符是连续的字母（例如"abc"或"zab"）。

2. 状态定义：

   • dp[i]：以第i个字符结尾的最长连续环绕子串的长度。

3. 状态转移方程：

   • 如果s[i]是s[i-1]的下一个字母（例如'a'是'z'的下一个字母），则dp[i] = dp[i-1] + 1。

   • 否则，dp[i] = 1。

4. 去重：

   • 使用哈希表hash记录以每个字母结尾的最长环绕子串的长度。

   • 最终结果是哈希表中所有值的累加。

     

---

代码逻辑详解

1. DP 表定义：

   • int n = s.size();

     • 获取字符串s的长度n。

   • vector<int> dp(n, 1);

     • 定义一个大小为n的数组dp，初始化为1，表示每个字符本身可以作为一个长度为1的环绕子串。

2. 填 DP 表：

   • for (int i = 1; i < n; i++)

     • 遍历字符串的每个字符，i表示当前字符的位置（从1开始）。

   • if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a'))

     • 检查当前字符是否是前一个字符的下一个字母：

       • s[i] - 1 == s[i - 1]：普通情况（例如'b'是'a'的下一个字母）。

       • s[i - 1] == 'z' && s[i] == 'a'：特殊情况（'a'是'z'的下一个字母）。

   • dp[i] = dp[i - 1] + 1;

     • 如果满足条件，则当前字符可以加入前面的环绕子串，长度加1。

3. 哈希表记录：

   • int hash[26] = {0};

     • 定义一个大小为26的数组hash，用于记录以每个字母结尾的最长环绕子串的长度。

   • for (int i = 0; i < n; i++)

     • 遍历字符串的每个字符。

   • hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);

     • 更新以当前字符结尾的最长环绕子串的长度。

4. 累加结果：

   • int sum = 0;

     • 定义一个变量sum，用于累加哈希表中的值。

   • for (auto x : hash)

     • 遍历哈希表。

   • sum += x;

     • 累加以每个字母结尾的最长环绕子串的长度。

5. 返回结果：

   • return sum;

     • 返回累加结果。

---

示例

假设输入字符串为：s = "zab"

执行过程：

1. 初始化：

   • dp = [1, 1, 1]

   • hash = [0, 0, 0, ..., 0]（26个0）

2. 填 DP 表：

   • i=1：

     • s[1] = 'a'，s[0] = 'z'，满足'a'是'z'的下一个字母。

     • dp[1] = dp[0] + 1 = 2。

   • i=2：

     • s[2] = 'b'，s[1] = 'a'，满足'b'是'a'的下一个字母。

     • dp[2] = dp[1] + 1 = 3。

3. 哈希表记录：

   • i=0：

     • s[0] = 'z'，dp[0] = 1。

     • hash['z' - 'a'] = max(0, 1) = 1。

   • i=1：

     • s[1] = 'a'，dp[1] = 2。

     • hash['a' - 'a'] = max(0, 2) = 2。

   • i=2：

     • s[2] = 'b'，dp[2] = 3。

     • hash['b' - 'a'] = max(0, 3) = 3。

4. 累加结果：

   • sum = 1 + 2 + 3 = 6。

5. 返回结果：6

---

总结

• 问题本质：动态规划解决环绕子串的计数问题。

• 核心思想：

  • 通过dp[i]记录以第i个字符结尾的最长环绕子串的长度。

  • 使用哈希表去重，记录以每个字母结尾的最长环绕子串的长度。

• 时间复杂度：O(n)，遍历字符串两次。

• 空间复杂度：O(n)，使用了一个大小为n的dp表和一个大小为26的哈希表。