一、最大子数组和
题目要求找到数组中连续子数组的最大和，子数组需连续且至少包含一个元素。核心思路是拆解为：以第 i 个元素结尾的最大子数组和，要么是将第 i 个元素加入前一个子数组，要么是从第 i 个元素重新开始。
我们定义 dp[i] 表示以第 i 个元素为结尾的连续子数组的最大和。状态转移方程为 dp[i] = max(dp[i-1] + nums[i], nums[i])。如果 dp[i-1] + nums[i] 更大，说明延续之前的子数组更优；反之则从当前元素重新开始。初始化时 dp[0] = nums[0]，遍历时维护一个变量记录全局最大值即可。
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;
}
};
二、环形子数组的最大和
对于环形数组，最大子数组可能不跨首尾（普通情况），也可能跨越首尾（环形情况）。跨越首尾的情况等价于总和减去中间某段最小子数组的和。
我们需要同时计算非环形的最大子数组和 fmax，以及最小子数组和 gmin。若所有元素均为负数，直接返回 fmax；否则比较 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);
}
};
三、乘积最大子数组
乘积问题比求和复杂，因为负负得正。因此需要同时跟踪以当前位置结尾的最大乘积 f[i] 和最小乘积 g[i]。
当遇到负数时，最大乘积可能变成最小，最小乘积可能变成最大。所以转移方程中要同时考虑 f[i-1] * nums[i] 和 g[i-1] * nums[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;
}
};
四、乘积为正数的最长子数组长度
目标是找出乘积为正的最长子数组长度。关键在于统计正数和负数的个数，或者更简单地，用两个状态分别记录以当前位置结尾的正乘积长度和负乘积长度。
遇到 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 及以上的等差子数组个数。如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，则以 i 结尾的新增等差子数组数量等于以 i-1 结尾的数量加 1。
注意初始化时前两个元素无法构成长度>=3的子数组，所以 dp[0] 和 dp[1] 为 0。最终结果是 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;
}
};
六、最长湍流子数组
湍流子数组要求相邻元素的比较符号交替翻转（如 <, >, <）。我们需要定义两个状态：以 i 结尾最后上升的长度 f[i] 和最后下降的长度 g[i]。
若 arr[i] > arr[i-1]，则 f[i] = g[i-1] + 1；若 arr[i] < arr[i-1]，则 g[i] = f[i-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;
}
};
七、单词拆分
判断字符串 s 能否被字典 wordDict 中的单词拼接而成。dp[i] 表示前 i 个字符能否拆分。若存在 j < i 使得 dp[j] 为 true 且 s[j...i-1] 在字典中，则 dp[i] 为 true。
使用哈希集合优化字典查找，时间复杂度可降至 O(n^2)。
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 是字母表的无限循环。关键在于以某个字符结尾的最长连续符合 base 规则的子串长度决定了该字符贡献的独特子串数量。
遍历 s，若当前字符与前一个字符连续（或 z->a），则长度加 1，否则重置为 1。最后按字符去重累加最大长度。
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;
}
};