动态规划：子数组与子串问题详解

• f[i] = max(nums[i], f[i-1] + nums[i])
• g[i] = min(nums[i], g[i-1] + nums[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);
    }
};

三、乘积最大子数组

乘积问题比求和复杂，因为负数乘以负数会变成正数。因此，我们需要同时维护以当前位置结尾的最大乘积和最小乘积。

1. 状态定义：
   • f[i] 表示以第 i 个元素为结尾的连续子数组的最大乘积。
   • g[i] 表示以第 i 个元素为结尾的连续子数组的最小乘积。
2. 状态转移：
   • 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]))
   • 注意这里需要比较三个值：当前元素本身、前一个最大乘积、前一个最小乘积。

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。

我们需要区分两种状态：以当前位置结尾的正数乘积子数组长度，和负数乘积子数组长度。

1. 状态定义：
   • f[i] 表示以第 i 个元素为结尾的乘积为正数的最长子数组长度。
   • g[i] 表示以第 i 个元素为结尾的乘积为负数的最长子数组长度。
2. 状态转移：
   • 若 nums[i] > 0：正数延续正数，负数延续负数。
   • 若 nums[i] < 0：正数需由之前的负数转换而来，负数由之前的正数转换而来。
   • 若 nums[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。

当发现 nums[i] - nums[i-1] == nums[i-1] - nums[i-2] 时，说明以 i 结尾的新增了一个等差数列，同时之前以 i-1 结尾的所有等差数列都可以延伸到 i。

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

六、最长湍流子数组

湍流子数组要求相邻元素的比较符号交替翻转（如 <, >, < 或 >, <, >）。

我们可以定义两个状态，分别记录以当前位置结尾的最后一次比较是上升还是下降时的最长长度。

1. 状态定义：
   • f[i]：最后呈现为'上升'趋势的最长湍流子数组长度。
   • g[i]：最后呈现为'下降'趋势的最长湍流子数组长度。
2. 状态转移：
   • 若 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;
    }
};

七、单词拆分

判断字符串能否被字典中的单词拼接而成。这是一个典型的线性 DP 问题。

dp[i] 表示前 i 个字符能否被拆分。对于每个位置 i，我们尝试所有可能的分割点 j，检查 dp[j-1] 是否为真且 s[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 是字母表的无限循环。

关键在于识别连续的字符序列。如果一个字符与前一个字符在 base 中是连续的（如 'a'->'b' 或 'z'->'a'），则可以延长当前连续子串的长度。

由于需要去重，我们记录以每个字符结尾的最长连续子串长度，最终累加这些长度即可得到唯一子串总数。

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