2708. 一个小组的最大实力值

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • 状态机DP

思路

1. 题意 & 思路概览

题目要从数组 nums 中选出一个非空子集，使得选中元素的乘积最大。 元素可以不连续，本质是“最大乘积子序列”，只要求集合非空。

难点在于：

  • 元素有正有负还有 0
  • 负数个数不同，乘积符号会来回翻转
  • 我们既要支持“选当前元素”，也要支持“跳过当前元素”

这正适合用「状态机 DP」：同时维护“当前前缀能得到的最大正乘积”和“最小负乘积”，并且每一步都有“用 / 不用当前元素”的分支。

2. 状态定义

设遍历到下标 i（0-based）时：

  • \(\text{mx}_i\)：在前 \(i\) 个元素中，能得到的 最大乘积（可以是正数或负数，只要值最大），对应代码里的 mx
  • \(\text{mi}_i\)：在前 \(i\) 个元素中，能得到的 最小乘积（数值最小，通常是最负），对应代码里的 mi

注意这里的状态不区分“正/负”两类容器，而是用“最大值”和“最小值”两个端点来承载所有情况：

  • 最大值里自然包含“最优正数乘积”
  • 最小值里自然包含“绝对值最大的负数乘积”

同时，这两个状态都只考虑 非空子集。

3. 初始化（初值）

对第一个元素 \(\text{nums}[0]\)：

只可能出现的非空子集就是 {nums[0]}，所以有： \[ \text{mx}_0 = \text{mi}_0 = \text{nums}[0] \] 对应代码：

1
long long mx = nums[0], mi = nums[0];

这样可以保证：

  1. 状态从一开始就只代表“非空子集”的乘积
  2. 不会出现“用 0 表示没选元素”这种暧昧情况，避免误把“空集合乘积”混进来

4. 状态转移（核心）

遍历到第 \(i\) 个元素（代码里是 x = nums[i]）时，前一状态是： \[ \text{mx}_{i-1}, \quad \text{mi}_{i-1} \] 在代码中先用临时变量保存：

1
long long x = nums[i], tmi = mi, tmx = mx;

表示： \[ tmx = \text{mx}_{i-1}, \quad tmi = \text{mi}_{i-1} \] 接下来，对当前这个元素 x 有三种典型选择：

  1. 不选 x： 保持原状态不变，仍然用之前的子集
    • 对最大值：候选之一是 \(\text{mx}_{i-1}\)
    • 对最小值：候选之一是 \(\text{mi}_{i-1}\)
  2. 只选 x 单独成一组：
    • 最大值候选之一是 x
    • 最小值候选之一也是 x
  3. 把 x 乘到之前的某个乘积上：
    • 乘到原来的最优最大值上
    • 或乘到原来的最劣最小值上（因为负数会翻转符号）

核心就是根据 x 的符号，决定“谁乘上 x 能变成最大 / 最小”。

4.1 当 \(x \ge 0\) 时

此时乘以 x 不会改变乘积的符号：

  • 原来的最大值乘以非负数，仍然是最大方向的候选
  • 原来的最小值乘以非负数，仍然是最小方向的候选

所以转移是： \[ \begin{aligned} \text{mx}_i &= \max\big( \text{mx}_{i-1},\ x,\ \text{mx}_{i-1} \cdot x \big) \\ \text{mi}_i &= \min\big( \text{mi}_{i-1},\ x,\ \text{mi}_{i-1} \cdot x \big) \end{aligned} \] 对应代码：

1
2
3
4
if (x >= 0) {
    mx = max(tmx, max(x, tmx * x));
    mi = min(tmi, min(x, tmi * x));
}

解释：

  • tmx：不选 x，继续用以前的最大乘积
  • x：只选当前这一位，重新开一个子集
  • tmx * x：在之前最大乘积的基础上再乘上 x
  • tmi * x 同理用于更新最小值

4.2 当 \(x < 0\) 时

此时乘以 x 会翻转符号：

  • 原来的最大值乘以负数，变成一个很小的负数，适合拿来更新“最小值”
  • 原来的最小值乘以负数，变成一个很大的正数，适合拿来更新“最大值”

因此： \[ \begin{aligned} \text{mx}_i &= \max\big( \text{mx}_{i-1},\ x,\ \text{mi}_{i-1} \cdot x \big) \\ \text{mi}_i &= \min\big( \text{mi}_{i-1},\ x,\ \text{mx}_{i-1} \cdot x \big) \end{aligned} \] 对应代码：

1
2
3
4
else { // x < 0
    mx = max(tmx, max(x, tmi * x)); // 用 tmi * x 来冲击最大值
    mi = min(tmi, min(x, tmx * x)); // 用 tmx * x 来冲击最小值
}

解释：

  • tmi * x：负数乘负数，可能产生最大的正数乘积，用来更新 mx
  • tmx * x：正数乘负数，可能产生最小的负数乘积，用来更新 mi
  • tmx 和 tmi 分别对应“不选当前元素”的情况
  • x 对应“只选当前元素”的新开子集

5. 为什么状态里要保留“旧值本身”（tmx / tmi）

经典的“最大乘积子数组”问题是 必须包含当前元素 的连续子数组，所以转移时不会用“旧值本身”作为候选，只比较： \[ x,\ \text{mx}_{i-1} \cdot x,\ \text{mi}_{i-1} \cdot x \] 而这道题是“子集 / 子序列”，允许跳过当前元素，所以：

  • 对最大值，tmx 代表“完全不选当前元素 x”
  • 对最小值，tmi 代表“完全不选当前元素 x”

这就是为什么代码里有：

1
2
mx = max(tmx, ...);
mi = min(tmi, ...);

等价于在状态转移中显式地加入一项“什么都不做”。

6. 最终答案

遍历完所有元素后，此时的 mx 就是： \[ \text{mx}_{n-1} = \max_{\emptyset \neq S \subseteq \{0,\dots,n-1\}} \prod_{i \in S} nums[i] \] 对应代码返回：

1
return mx;

因为初始化时就用 nums[0]，并且在每一步转移中，候选里都包含“只选当前元素 x”这一项，所以整个过程始终是在所有 非空子集 的乘积中取最大值，不会出现“空集合”的情况。

7. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long maxStrength(vector<int>& nums) {
        long long mx = nums[0], mi = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            long long x = nums[i], tmi = mi, tmx = mx;
            if (x >= 0) {
                mx = max(tmx, max(x, tmx * x));
                mi = min(tmi, min(x, tmi * x));
            } else {
                mx = max(tmx, max(x, tmi * x));
                mi = min(tmi, min(x, tmx * x));
            }
        }
        return mx;
    }
};