动态规划：子数组与子串问题
一、最大子数组和
这道题要求找到数组中连续子数组的最大和。核心在于思考以第 i 个元素结尾的子数组，是延续前面的结果，还是从当前重新开始。
我们定义 dp[i] 为以第 i 个元素结尾的连续子数组的最大和。对于每个位置，只有两种选择：要么把当前元素加到前一个子数组后面（如果前一个和是正的），要么直接从当前元素开始新的一段。状态转移方程就是 dp[i] = max(dp[i-1] + nums[i], nums[i])。
初始化时，dp[0] 就是第一个元素本身。遍历过程中，我们需要维护一个全局最大值 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;
}
};
二、环形子数组的最大和
数组变成环形后，最大子数组有两种可能：一种是普通的非环形子数组，另一种是跨越首尾的环形子数组。后者实际上等于总和减去中间那段最小子数组的和。
我们需要同时计算两个 DP 数组：f[i] 记录以 i 结尾的最大子数组和，g[i] 记录以 i 结尾的最小子数组和。遍历结束后，比较普通情况下的最大值 fmax 和环形情况下的 sum - gmin。注意一种特殊情况：如果所有数都是负数，最小子数组和等于总和，此时不能取环形结果，应直接返回 fmax。
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);
}
};
三、乘积最大子数组
乘积问题比求和复杂，因为负数乘以负数会变成正数。这意味着在某个位置，当前的最小值可能在下一步变成最大值。因此，我们需要同时维护以当前位置结尾的最大乘积 f[i] 和最小乘积 g[i]。
状态转移时，对于 f[i]，我们要考虑三种来源：当前元素本身、前一个最大乘积乘当前元素、前一个最小乘积乘当前元素（负负得正）。同理 g[i] 也要取三者中的最小值。遍历时更新全局最大值即可。
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;
}
};
四、乘积为正数的最长子数组长度
这里关注的是长度，且只关心乘积的正负。我们需要跟踪两个状态：以 i 结尾的乘积为正的最长长度 f[i]，以及乘积为负的最长长度 g[i]。
遇到 0 时，两个长度都归零。遇到正数时，正长度延续正长度，负长度延续负长度。遇到负数时，正长度会继承之前的负长度（负负得正），而负长度则继承之前的正长度。注意边界条件，如果之前没有负长度，遇到负数后正长度暂时为 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。
我们用 dp[i] 表示以 i 结尾的等差子数组个数。如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，则 dp[i] = dp[i-1] + 1，否则为 0。最后将所有 dp 值累加即为答案。注意数组长度小于 3 时直接返回 0。
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;
}
};
六、最长湍流子数组
湍流子数组要求相邻元素的比较符号交替翻转。我们可以定义两个状态：f[i] 表示以 i 结尾且最后一步是上升的最长长度，g[i] 表示最后一步是下降的最长长度。
如果当前大于前一个，说明是上升，那么它必须接在前一个下降的状态后面，即 f[i] = g[i-1] + 1。反之亦然。如果相等，则重置为 1。初始时所有位置设为 1，遍历过程中记录最大值。
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;
}
};
七、单词拆分
判断字符串能否被字典中的单词拼接而成。这是一个典型的区间 DP 或线性 DP 问题。dp[i] 表示前 i 个字符能否被拆分。
状态转移时，枚举分割点 j，如果 dp[j-1] 为真且子串 s[j-1...i-1] 在字典中，则 dp[i] 为真。为了快速查找，将字典转为哈希集合。初始化 dp[0] 为 true，表示空字符串可拆分。
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];
}
};
八、环绕字符串中唯一的子字符串
base 是字母表的无限循环，子串需满足字符连续。统计不同子串数量时，关键在于去重。以某个字符结尾的最长合法子串长度，决定了该字符能贡献多少种不同的后缀。
先计算 dp[i] 表示以 s[i] 结尾的最长连续长度。然后维护一个长度为 26 的数组 arr，记录每个字符结尾出现过的最大长度。最终答案是 arr 中所有值的和，这样自然避免了重复计数。
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;
}
};