3290. 最高乘法得分

发表于 2025-12-19 分类于力扣阅读次数： Waline：本文字数： 843 阅读时长 ≈ 3 分钟

考点

思路

一、问题概述

给定两个整数数组：

a：长度为 4
b：长度为 n (n ≥ 4)

需要从数组 b 中按原有顺序选择 4 个不同的位置 设选中的下标为： \[ 0 \le i_1 < i_2 < i_3 < i_4 < n \] 目标是最大化以下得分函数： \[ a_0 \cdot b_{i_1} + a_1 \cdot b_{i_2} + a_2 \cdot b_{i_3} + a_3 \cdot b_{i_4} \]

二、动态规划建模

1. 状态定义

定义二维 DP 数组： \[ f[i][k] \] 表示：

只考虑数组 b 的前 i 个元素（下标 0 \sim i-1），并且已经选择了 k 个点时，所能得到的最大得分

其中：

\(i = 0 \sim n\)
\(k = 0 \sim 4\)

2. 初始值（Initialization）

当没有选任何点时，得分为 0： \[ f[0][0] = 0 \]
其余不合法状态设为负无穷（表示不可能达到）： \[ f[0][k] = -\infty \quad (k \ge 1) \]

在代码中，通常用一个极小负数（如 LLONG_MIN >> 1）来模拟 \(-\infty\)，以避免溢出。

3. 状态转移方程（Transition）

对于第 i 个元素 b[i-1]，有两种选择：

情况一：不选第 `i` 个元素

\[ f[i][k] = f[i-1][k] \]

情况二：选第 `i` 个元素作为第 `k` 个被选中的点

\[ f[i][k] = f[i-1][k-1] + b_{i-1} \cdot a_{k-1} \]

综合转移公式

\[ \boxed{ f[i][k] = \max \left( f[i-1][k],\; f[i-1][k-1] + b_{i-1} \cdot a_{k-1} \right) } \quad (1 \le k \le 4) \]

关键点：转移必须全部来自 i-1 层状态，否则会导致同一个 b[i-1] 被重复选用。

4. 答案（Answer）

最终答案即为： \[ \boxed{f[n][4]} \] 表示在整个数组 b 中选取 4 个点所能获得的最大得分。

三、二维 DP 实现（原始版本）

class Solution {
public:
    static const int maxn = 1e5 + 5, neg = INT_MIN >> 1;
    long long maxScore(vector<int>& a, vector<int>& b) {
        long long f[maxn][5], n = b.size();
        memset(f, 0xcf, sizeof(f));
        for (int i = 1; i <= n; ++i) {
            f[i][1] = max(f[i - 1][1], 1LL * b[i - 1] * a[0]);
            if (i >= 2)
                f[i][2] = max(f[i - 1][2], f[i - 1][1] + 1LL * b[i - 1] * a[1]);
            if (i >= 3)
                f[i][3] = max(f[i - 1][3], f[i - 1][2] + 1LL * b[i - 1] * a[2]);
            if (i >= 4)
                f[i][4] = max(f[i - 1][4], f[i - 1][3] + 1LL * b[i - 1] * a[3]);
        }
        return f[n][4];
    }
};

四、空间优化：滚动数组（一维 DP）

观察状态转移可知：

第 i 层状态 只依赖第 i-1 层
k 的最大值固定为 4

因此可以将二维数组压缩为 4 个变量，实现 O(1) 额外空间。

一维状态含义

one：已选 1 个点的最大得分
two：已选 2 个点的最大得分
three：已选 3 个点的最大得分
four：已选 4 个点的最大得分

每轮循环中使用临时变量保存新状态，避免覆盖旧值。

滚动数组实现代码

class Solution {
public:
    static const int maxn = 1e5 + 5;
    static const long long neg = LLONG_MIN >> 1;
    long long maxScore(vector<int>& a, vector<int>& b) {
        long long one = neg, two = neg, three = neg, four = neg, n = b.size();
        for (int i = 1; i <= n; ++i) {
            long long One = neg, Two = neg, Three = neg, Four = neg;
            One = max(one, 1LL * b[i - 1] * a[0]);
            if (i >= 2)
                Two = max(two, one + 1LL * b[i - 1] * a[1]);
            if (i >= 3)
                Three = max(three, two + 1LL * b[i - 1] * a[2]);
            if (i >= 4)
                Four = max(four, three + 1LL * b[i - 1] * a[3]);
            one = One, two = Two, three = Three, four = Four;
        }
        return four;
    }
};

五、复杂度分析

时间复杂度： \[ O(n \times 4) = O(n) \]
空间复杂度：
- 二维 DP：\(O(n \times 4)\)
- 滚动数组：\(\boxed{O(1)}\)

考点

思路