3434. 子数组操作后的最大频率

发表于 2025-12-17 分类于力扣阅读次数： Waline：本文字数： 2.2k 阅读时长 ≈ 7 分钟

考点

状态机DP
高难度的滚动数组

思路

记号与约定

设数组长度为 \(n\)，并用 1-based 记号 \(a_i=\texttt{nums}[i-1]\)。
设目标值为 \(k\)。
指示函数用 \(\mathbf{1}[\cdot]\) 表示，且条件内部统一使用 ==，例如 \(\mathbf{1}[a_i == k]\)。

1. 贪心为何不可行

一次操作选择子数组 \([l,r]\) 并对其中每个元素加同一个整数 \(x\)。若希望某个位置最终等于 \(k\)，必须满足 \[ a_i + x = k \quad\Longleftrightarrow\quad a_i = k - x. \] 因此一次操作最多把某一个固定值 \(t=k-x\) 的元素整体推到 \(k\)，并不能把“所有 <k 的元素”都推到 \(k\)。

更关键的是：若子数组中原本就有 \(k\)，它们会变为 \(k+x\)，从而离开 \(k\)。于是选择区间的优劣取决于“能变成 \(k\) 的数量”与“被推走的 \(k\) 的数量”的差值，而不是区间长度、也不是 <k 连续段长度。

2. 方法一：枚举 \(x\) + 最大子段和（二维 DP 讲解重点）

2.1 固定 \(x\) 的贡献建模

固定一次操作的加数 \(x\)。对每个位置定义净贡献： \[ d_i=\begin{cases} +1,& a_i == k-x,\\ -1,& a_i == k,\\ 0,& \text{otherwise}. \end{cases} \] 若对区间 \([l,r]\) 施加该 \(x\)，则最终 \(k\) 的净增量为 \[ \Delta(l,r;x)=\sum_{i=l}^{r} d_i. \] 因此对固定 \(x\)，最优子数组就是 \[ \max_{1\le l\le r\le n}\sum_{i=l}^{r} d_i, \] 这正是经典最大子数组和（Kadane）问题。

设原数组中 \(k\) 的出现次数为 \[ \mathrm{cnt}_k=\sum_{i=1}^{n}\mathbf{1}[a_i == k]. \] 总答案为 \[ \mathrm{ans}=\mathrm{cnt}_k+\max_{x\in X}\Big(\max_{l\le r}\sum_{i=l}^{r} d_i\Big), \] 其中候选集合 \(X\) 可取为 \(\{\,k-a_i\,\}\)，因为只有这类 \(x\) 才可能产生 +1 的收益。

2.2 `x == 0` 必须特判的原因（核心易错点）

当 \(x==0\) 时，操作等价于“不操作”，净增量应恒为 0。

但若仍使用如下判定顺序：

若 \(a_i == k-x\) 则 \(d_i=+1\)
否则若 \(a_i == k\) 则 \(d_i=-1\)

则当 \(x==0\) 时 \(k-x==k\)，所有 \(a_i==k\) 会命中第一条而变成 \(d_i=+1\)，相当于把“不操作”误计为“收益”。因此外层必须跳过 x==0（或显式令该情况下 \(d_i\equiv 0\)）。

2.3 二维 DP 状态定义与转移

二维实现使用两类状态：

\(f[i][0]\)：以位置 \(i\) 结尾的最大子数组和
\(f[i][1]\)：处理完前 \(i\) 个元素后（前缀内）出现过的最大子数组和（不要求以 \(i\) 结尾）

初始化（与代码一致）： \[ f[0][0]=0,\qquad f[0][1]=-\infty. \] 其中 \(f[0][1]\) 取负无穷用于严格表达“前缀最优尚未形成”，避免边界被误继承。

转移（对 \(i=1..n\)）： \[ \begin{aligned} f[i][0] &= \max\{f[i-1][0],\,0\}+d_i,\\ f[i][1] &= \max\{f[i-1][0],\,f[i-1][1]\}. \end{aligned} \] 含义如下：

\(f[i][0]\)：若上一段和为正则延续，否则从 \(i\) 重新开段（取 0），再加上 \(d_i\)。
\(f[i][1]\)：维护截至当前位置的历史最大值。

对固定 \(x\)，最大净增量为 \[ \max_{1\le i\le n}\max\{f[i][0],f[i][1]\}. \] 全体 \(x\) 取最大后，再加上 \(\mathrm{cnt}_k\) 即为最终答案。

2.4 方法一：二维 AC 代码（重点讲解对象）

class Solution {
public:
    static const int maxn = 1e5 + 5;
    int maxFrequency(vector<int>& nums, int k) {
        int c = 0;
        unordered_set<int> st;
        for (int& x : nums) {
            st.insert(k - x);
            if (x == k)
                ++c;
        }
        int f[maxn][2], s = 0, n = nums.size();
        for (auto& x : st) {
            f[0][0] = 0, f[0][1] = INT_MIN >> 1;
            if (!x)
                continue;
            for (int i = 1; i <= n; ++i) {
                int y = nums[i - 1], d;
                if (y == k - x)
                    d = 1;
                else if (y == k)
                    d = -1;
                else
                    d = 0;
                f[i][0] = max(f[i - 1][0], 0) + d;
                f[i][1] = max(f[i - 1][0], f[i - 1][1]);
                s = max(s, max(f[i][0], f[i][1]));
            }
        }
        return s + c;
    }
};

2.5 方法一：滚动数组版

class Solution {
public:
    static const int maxn = 1e5 + 5;
    int maxFrequency(vector<int>& nums, int k) {
        int c = 0;
        unordered_set<int> st;
        for (int& x : nums) {
            st.insert(k - x);
            if (x == k)
                ++c;
        }
        int s = 0, n = nums.size();
        for (auto& x : st) {
            int a = 0, b = INT_MIN >> 1;
            if (!x)
                continue;
            for (int i = 1; i <= n; ++i) {
                int y = nums[i - 1], d;
                if (y == k - x)
                    d = 1;
                else if (y == k)
                    d = -1;
                else
                    d = 0;
                b = max(a, b), a = max(a, 0) + d, s = max(s, max(a, b));
            }
        }
        return s + c;
    }
};

3. 方法二：三段状态机 DP（二维 3 状态讲解重点）

该方法固定一个 \(\texttt{target}\)（表示希望把值 target 通过一次加法变成 \(k\)），将数组分成：

左段：不修改，只统计 \(k\)
中段：被修改的子数组，只统计 target（它们会变成 \(k\)），且中段内的 \(k\) 不可统计
右段：不修改，只统计 \(k\)

3.1 状态定义（对每个 target 单独计算）

处理完前 \(i\) 个元素（即前缀 \(a_1..a_i\)）后：

\(f[i][0]\)：处于“左段”的最大可得 \(k\) 数
\(f[i][1]\)：处于“左+中段”的最大可得 \(k\) 数（中段统计 target）
\(f[i][2]\)：处于“左+中+右段”的最大可得 \(k\) 数（右段继续统计 \(k\)）

3.2 状态转移（对 \(i=1..n\)）

\[ \begin{aligned} f[i][0] &= f[i-1][0] + \mathbf{1}[a_i == k],\\ f[i][1] &= \max\{f[i-1][0], f[i-1][1]\} + \mathbf{1}[a_i == \texttt{target}],\\ f[i][2] &= \max\{f[i-1][1], f[i-1][2]\} + \mathbf{1}[a_i == k]. \end{aligned} \]

3.3 初值与答案

二维 AC 代码采用严格初值： \[ f[0][0]=0,\qquad f[0][1]=f[0][2]=-\infty, \] 表示起点只能在左段，不允许“凭空进入中段/右段”。

扫描过程中取 \[ \max\{f[i][0], f[i][1], f[i][2]\} \] 更新全局最优即可（与代码一致）。

3.4 方法二：二维 AC 代码（重点讲解对象）

class Solution {
public:
    static const int maxn = 1e5 + 5, neg = INT_MIN >> 1;
    int maxFrequency(vector<int>& nums, int k) {
        unordered_set<int> st;
        for (int& x : nums)
            st.insert(x);
        int f[maxn][3], n = nums.size(), res = 0;
        for (auto& target : st) {
            f[0][0] = 0, f[0][1] = f[0][2] = neg;
            for (int i = 1; i <= n; ++i) {
                int x = nums[i - 1];
                f[i][0] = f[i - 1][0] + (x == k);
                f[i][1] = max(f[i - 1][0], f[i - 1][1]) + (x == target);
                f[i][2] = max(f[i - 1][1], f[i - 1][2]) + (x == k);
                res = max(res, max(f[i][0], max(f[i][1], f[i][2])));
            }
        }
        return res;
    }
};

3.5 方法二：滚动数组版

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        unordered_set<int> st(nums.begin(), nums.end());
        int ans = 0;
        for (auto& target : st) {
            int a = 0, b = 0, c = 0;
            for (int& x : nums) {
                c = max(b, c) + (x == k);
                b = max(a, b) + (x == target);
                a = a + (x == k);
                ans = max(ans, max(b, c));
            }
        }
        return ans;
    }
};

4. 方法三：方法二的升级（并行维护全部 target；依赖单调性延迟更新）

方法三不再外层枚举 target，而是同时维护所有 target 的“左+中段”状态。关键点是：左段计数 \(f0[i]\) 单调不减，因此中段状态与 \(f0\) 的比较可以延迟到“该 target 出现的时刻”再做。

4.1 下标形式的严格定义（按 \(f0[i]=f0[i-1]+\cdots\) 的风格）

定义： \[ f0[i]=\sum_{j=1}^{i}\mathbf{1}[a_j == k],\qquad f0[0]=0, \] 显然 \(f0[i]\) 单调不减。

对每个取值 \(t\in[1,50]\)，定义中段状态： \[ f1_t[i] = \text{处理到 }i\text{ 且处于“左+中段”，中段 target }==t\text{ 时的最优值}. \] 若按方法二逐个 \(t\) 推导，则应满足递推： \[ f1_t[i]=\max\{f1_t[i-1],\ f0[i-1]\}+\mathbf{1}[a_i == t], \qquad f1_t[0]=0. \] 再定义右段（已进入右段）的最优： \[ f2[i]=\max\Big\{f2[i-1],\ \max_{t} f1_t[i-1]\Big\}+\mathbf{1}[a_i == k], \qquad f2[0]=0. \]

4.2 延迟更新的数学原因（核心结论）

对固定 \(t\)，若在某一段区间内 \(a_i \ne t\)，则该段内 \[ f1_t[i]=\max\{f1_t[i-1],\ f0[i-1]\} \] 仅做“与 \(f0\) 取最大”的提升，并不会产生 \(+1\)。

由于 \(f0[i]\) 单调不减，任意时刻 \(i\) 都有： \[ \max_{0\le j\le i-1} f0[j] = f0[i-1]. \] 因此在两次出现 \(t\) 之间，把 \(f1_t\) 反复与 \(f0\) 取最大，等价于在下一次 \(t\) 出现时一次性执行 \[ f1_t \leftarrow \max\{f1_t,\ f0[i-1]\}, \] 随后再加上本次出现带来的 \(+1\)。

这正是实现中只更新 f1[x]（其中 \(x=a_i\)）而不需要每轮遍历所有 \(t\) 的根本原因。

4.3 方法三：AC 代码

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int f0 = 0, f1[51], f2 = 0, mx_f1 = 0, mx_f2 = 0;
        memset(f1, 0, sizeof(f1));
        for (int& x : nums) {
            f2 = max(f2, mx_f1) + (x == k), mx_f2 = max(mx_f2, f2);
            f1[x] = max(f1[x], f0) + 1, mx_f1 = max(mx_f1, f1[x]);
            f0 += (x == k);
        }
        return max(f0, max(mx_f1, mx_f2));
    }
};

5. 小结

方法一将“固定 \(x\) 的净增量”转化为最大子段和，核心在于贡献定义、x==0 特判、初值与 Kadane 转移。
方法二用三段状态机表达“左/中/右”，核心在于二维三状态的严格语义、\(-\infty\) 初值与转移依赖方向。
方法三将方法二的外层枚举并行化，核心在于 \(f0[i]=f0[i-1]+\mathbf{1}[a_i == k]\) 的单调性，从而允许对 \(f1_t\) 执行延迟比较更新，并用 mx_f1 支持 \(f2\) 的转移。

考点

思路