动态规划实战：子数组与子串问题解析

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