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

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