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

• 一、[最大子数组和](https://leetcode.cn/problems/maximum-subarray/description/)
• 二、[环形子数组的最大和](https://leetcode.cn/problems/maximum-sum-circular-subarray/description/)
• 三、[乘积最大子数组](https://leetcode.cn/problems/maximum-product-subarray/description/)
• 四、[乘积为正数的最长子数组长度](https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/)
• 五、[等差数列划分](https://leetcode.cn/problems/arithmetic-slices/description/)
• 六、[最长湍流子数组](https://leetcode.cn/problems/longest-turbulent-subarray/description/)
• 七、[单词拆分](https://leetcode.cn/problems/word-break/description/)
• 八、[环绕字符串中唯一的子字符串](https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/)
• 结尾

一、最大子数组和

题目描述：

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

编写代码：

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 个元素重新开始，最后通过整个数组的和 – 最小数组和，得到最大数组和

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

编写代码：

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);
}
};

三、乘积最大子数组

题目描述：

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

编写代码：

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），需要区分两种状态跟踪子数组长度。以下是具体思路：

编写代码：

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。以下是具体思路：

编写代码：

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;
}
};

六、最长湍流子数组

题目描述：

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

编写代码：

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 的子串在字典中。以下是具体思路：

编写代码：

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”），以某个字符结尾的符合条件的子串，其最长长度决定了该字符贡献的独特子串数量。以下是本道题的具体思路：

编写代码：

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;
}
};

结尾

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