题目描述

给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers，其中 n >= m，数组下标 从 1 开始 计数。

初始时，你的分数为 0。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：

• 选择数组 nums 开头处或者末尾处 的整数 x。
• 你获得 multipliers[i] * x 分，并累加到你的分数中。
• 将 x 从数组 nums 中移除。

在执行 m 步操作后，返回 最大 分数。

样例

输入：nums = [1,2,3], multipliers = [3,2,1]
输出：14
解释：一种最优解决方案如下：
- 选择末尾处的整数 3，[1,2,3] ，得 3 * 3 = 9 分，累加到分数中。
- 选择末尾处的整数 2，[1,2] ，得 2 * 2 = 4 分，累加到分数中。
- 选择末尾处的整数 1，[1] ，得 1 * 1 = 1 分，累加到分数中。
总分数为 9 + 4 + 1 = 14。

输入：nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
输出：102
解释：一种最优解决方案如下：
- 选择开头处的整数 -5，[-5,-3,-3,-2,7,1] ，得 -5 * -10 = 50 分，累加到分数中。
- 选择开头处的整数 -3，[-3,-3,-2,7,1] ，得 -3 * -5 = 15 分，累加到分数中。
- 选择开头处的整数 -3，[-3,-2,7,1] ，得 -3 * 3 = -9 分，累加到分数中。
- 选择末尾处的整数 1，[-2,7,1] ，得 1 * 4 = 4 分，累加到分数中。
- 选择末尾处的整数 7，[-2,7] ，得 7 * 6 = 42 分，累加到分数中。
总分数为 50 + 15 - 9 + 4 + 42 = 102。

限制

• n == nums.length
• m == multipliers.length
• 1 <= m <= 10^3
• m <= n <= 10^5
• -1000 <= nums[i], multipliers[i] <= 1000

算法

(动态规划) $O(m^2)$

1. 设状态 $f(i, j)$ 表示取了 $i$ 个数字，其中从头部取了 $j$ 个数字时的最大值。
2. 初始时 $f(0, 0) = 0$，其余待定。
3. 转移时，对于第 $i$ 次取数字，并从头部取 $j$ 个数字时：
   • 如果 $j \ge 1$ 则可以从 $f(i - 1, j - 1)$ 转移，表示这一次是从头部取数字，并累加本次取头部的分数。
   • 如果 $i - j \ge 1$，则可以从 $f(i - 1, j)$ 转移，表示这一次从尾部取数字，并累加本次从尾部取的分数。
4. 最终答案为 $\max(f(m, i))$。

时间复杂度

• 状态数为 $O(m^2)$，转移时间为常数，故总时间复杂度为 $O(m^2)$。

空间复杂度

• 需要 $O(m^2)$ 的空间存储状态。

C++ 代码

#define M 1010

class Solution {
private:
    int f[M][M];

public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        const int n = nums.size(), m = multipliers.size();
        f[0][0] = 0;

        for (int i = 1; i <= m; i++)
            for (int j = 0; j <= i; j++) {
                f[i][j] = INT_MIN;
                int p = multipliers[i - 1];
                if (j >= 1)
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + p * nums[j - 1]);
                if (i - j >= 1)
                    f[i][j] = max(f[i][j], f[i - 1][j] + p * nums[n - (i - j)]);
            }

        int ans = INT_MIN;
        for (int i = 0; i <= m; i++)
            ans = max(ans, f[m][i]);

        return ans;
    }
};