3473. 长度至少为 M 的 K 个子数组之和

发表于 2025-12-03 更新于 2025-12-04 分类于力扣阅读次数： Waline：本文字数： 1.5k 阅读时长 ≈ 5 分钟

考点

划分DP
前缀和
数学
区间长度限制下的剪枝

思路

1. 问题结构与经典划分 DP 的基本形式

我们希望在数组 \[ a[1..n] \] 中选出 \(k\) 个不重叠子数组，使得每个子数组长度至少为 \(m\)，并最大化它们的元素和。

一个最自然的 DP 状态是： \[ f[j][i] = \text{前 } i \text{ 个元素中恰好选 } j \text{ 段子数组的最大值} \] 这里的所有子数组都已完全落在 \([1..i]\) 中，也就是说我们不处理“未完成但长度不够 m 的残段”。

基本思考结构如下：

若第 \(j\) 段不以 \(i\) 结尾，那么 \[ f[j][i] = f[j][i-1] \]
若第 \(j\) 段以 \(i\) 结尾，则必有某个左端点 \(l\)，满足 \[ l \le i - m + 1,\qquad \text{且 } l - 1 \ge (j-1)m \] 其中长度约束 \(i-l+1 \ge m\) 和「前 \(j-1\) 段至少消耗了 \((j-1)m\) 个元素」保证段合法性。

于是本段的贡献为 \[ \text{seg}(l,i) = \sum_{t=l}^i a[t] \] 而前 \(j-1\) 段的贡献是 \[ f[j-1][l-1] \] 因此，以 \(i\) 为右端点的方案为： \[ f[j][i] = \max_{l \in [(j-1)m+1 .. i-m+1]} \left( f[j-1][l-1] + \text{seg}(l,i) \right) \] 这是一个典型的 “枚举最后一段左端点” 的 \(O(nk \cdot n)\) DP，不够快。

2. 引入前缀和，将区间和写成差值形式

令 \[ pre[i] = \sum_{t=1}^i a[t], \qquad pre[0]=0 \] 则 \[ \text{seg}(l,i) = pre[i] - pre[l-1] \] 代回前式： \[ f[j][i] = \max\left( f[j][i-1],\; \max_{l=(j-1)m+1}^{i-m+1} \left( f[j-1][l-1] - pre[l-1] + pre[i] \right) \right) \] 为方便书写设 \[ t = l-1 \] 则 \(t\) 的范围变为 \[ t \in [(j-1)m .. i-m] \] 转移化为： \[ f[j][i] = \max\left( f[j][i-1], \max_{t=(j-1)m}^{i-m}\bigl(f[j-1][t] - pre[t]\bigr) + pre[i] \right) \] 可以看到，「对每个 \(i\) 求区间最大值」成为瓶颈。

3. 核心优化：将区间最大值转化为前缀最大值

对固定的 \(j\)，当我们从左到右扫描 \(i\) 时，可逐渐维护一个随 \(i\) 增长的前缀最大值： \[ mx(i) = \max_{t=(j-1)m}^{i-m} \bigl(f[j-1][t] - pre[t]\bigr) \] 当每次 \(i\) 增加 1，新加入的候选 \(t = i - m\)，只需更新： \[ mx = \max\bigl(mx,\; f[j-1][i-m] - pre[i-m]\bigr) \] 于是更新公式变成 O(1)： \[ f[j][i] = \max\left( f[j][i-1],\; mx + pre[i] \right) \] 并且只有当 \(i - m \ge (j-1)m\) 时，才允许更新 \(mx\)；影响范围清晰明确。

4. 编程结构：按 j 层层推进，按 i 单调扫描

完整思路如下。

预处理前缀和 \(pre[i]\)
初始化： \[ f[0][i] = 0,\quad \forall i \]
对每个 \(j = 1..k\)：
- 设合法的最早右端点为 \(i = j*m\)
- 初始化 \[ mx = -\infty,\quad p=(j-1)m \]
- 对每个 \(i\) 从左到右扫描：
  - 不以 \(i\) 为右端点： \[ f[j][i] = f[j][i-1] \]
  - 若 \(i-m \ge p\)，即可向 mx 加入新候选： \[ mx = \max(mx,\; f[j-1][i-m] - pre[i-m]) \] 并尝试以 \(i\) 结尾： \[ f[j][i] = \max(f[j][i],\; mx + pre[i]) \]
最终答案： \[ f[k][n] \]

得到AC代码如下：

class Solution {
 public:
  const int neg = 0xcfcfcfcf;
  int maxSum(vector<int>& nums, int k, int m) {
    int f[2005][2005], pre[2005];
    int n = nums.size();
    pre[0] = 0;
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + nums[i - 1];
    memset(f, 0xcf, sizeof(f));
    for (int i = 0; i <= n; ++i) f[0][i] = 0;
    for (int j = 1; j <= k; ++j) {
      int mx = neg, p = (j - 1) * m;
      for (int i = j; i <= n; ++i) {
        if (f[j][i - 1] != neg) f[j][i] = max(f[j][i], f[j][i - 1]);
        if (i - m >= p && f[j - 1][i - m] != neg) {
          mx = max(mx, f[j - 1][i - m] - pre[i - m]);
          f[j][i] = max(f[j][i], mx + pre[i]);
        }
      }
    }
    return f[k][n];
  }
};

可以滚动数组，进一步减少常数开销：

class Solution {
public:
    const int neg = 0xcfcfcfcf;
    int maxSum(vector<int>& nums, int k, int m) {
        int f[2][2005], pre[2005];
        int n = nums.size();
        pre[0] = 0;
        for (int i = 1; i <= n; ++i)
            pre[i] = pre[i - 1] + nums[i - 1];
        for (int i = 0; i <= n; ++i)
            f[0][i] = 0;
        for (int j = 1; j <= k; ++j) {
            int mx = neg, p = (j - 1) * m;
            memset(f[j&1],0xcf,sizeof(f[j&1]));
            for (int i = j; i <= n; ++i) {
                f[j & 1][i] = neg;
                if (f[j & 1][i - 1] != neg)
                    f[j & 1][i] = max(f[j & 1][i], f[j & 1][i - 1]);
                if (i - m >= p && f[j - 1 & 1][i - m] != neg) {
                    mx = max(mx, f[j - 1 & 1][i - m] - pre[i - m]);
                    f[j & 1][i] = max(f[j & 1][i], mx + pre[i]);
                }
            }
        }
        return f[k & 1][n];
    }
};

5. 剪枝优化

循环应从 i = j * m 开始：

数学上我们知道，选 j 个子数组、每个长度 ≥ m，则总长度至少为 j * m
所以前 j * m - 1 个位置上，f[j][i] 一定是非法状态（应为负无穷）
所以从 j 或 j * m 开始，正确性不变

上界应设定为i <= n - (k - j) * m ：

当前已经要选 j 个子数组，剩下的还有 k - j 个，每个至少要 m 长，所以在右边必须至少留下 (k - j) * m 个元素给后面的子数组，也就是提前做了「右侧空间不够就没必要继续算」的剪枝

class Solution {
 public:
  const int neg = 0xcfcfcfcf;
  int maxSum(vector<int>& nums, int k, int m) {
    int f[2005][2005], pre[2005], n = nums.size();
    pre[0] = 0;
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + nums[i - 1];
    memset(f, 0xcf, sizeof(f));
    for (int i = 0; i <= n; ++i) f[0][i] = 0;
    for (int j = 1; j <= k; ++j) {
      int mx = neg;
      for (int i = j * m; i <= n - (k - j) * m; ++i) {
        f[j][i] = max(f[j][i], f[j][i - 1]);
        if (f[j - 1][i - m] != neg) {
          mx = max(mx, f[j - 1][i - m] - pre[i - m]);
          f[j][i] = max(f[j][i], mx + pre[i]);
        }
      }
    }
    return f[k][n];
  }
};

同样也可以进行滚动数组：

class Solution {
 public:
  const int neg = 0xcfcfcfcf;
  int maxSum(vector<int>& nums, int k, int m) {
    int f[2][2005], pre[2005], n = nums.size();
    pre[0] = 0;
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + nums[i - 1];
    for (int i = 0; i <= n; ++i) f[0][i] = 0;
    for (int j = 1; j <= k; ++j) {
      int mx = neg;
      memset(f[j & 1], 0xcf, sizeof(f[j & 1]));
      for (int i = j * m; i <= n - (k - j) * m; ++i) {
        f[j & 1][i] = max(f[j & 1][i], f[j & 1][i - 1]);
        if (f[j - 1 & 1][i - m] != neg) {
          mx = max(mx, f[j - 1 & 1][i - m] - pre[i - m]);
          f[j & 1][i] = max(f[j & 1][i], mx + pre[i]);
        }
      }
    }
    return f[k & 1][n];
  }
};