Hard

题目描述

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

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

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

请你返回执行 m 次操作后，能够获得的 最高分数。

示例 1：

输入：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

示例 2：

输入：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 <= 300
  • m <= n <= 10^5
  • -1000 <= nums[i], multipliers[i] <= 1000

解题思路

解题思路

这是一道典型的动态规划问题。题目要求我们每次只能从数组的开头或末尾取元素，这种限制让我们无法使用贪心算法。

状态定义

定义 dp[i][left] 表示执行了 i 次操作，从左边取了 left 个元素时能获得的最大分数。

那么从右边取的元素个数就是 i - left 个。当前剩余的数组范围是 [left, n-1-(i-left)]，即 [left, n-i+left-1]。

状态转移

对于第 i 次操作，我们有两种选择：

  1. 从左边取：dp[i][left] = dp[i-1][left-1] + nums[left-1] * multipliers[i-1]
  2. 从右边取：dp[i][left] = dp[i-1][left] + nums[n-1-(i-1-left)] * multipliers[i-1]

取两者的最大值作为 dp[i][left] 的值。

优化空间

由于每一步只依赖于前一步的结果，我们可以使用滚动数组将空间复杂度从 O(m²) 优化到 O(m)。

边界条件

  • dp[0][0] = 0：没有执行任何操作时分数为0
  • 对于每一步，left 的取值范围是 [0, min(i, m)]

最终答案是 max(dp[m][left]) for all valid left。

代码实现

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n = nums.size(), m = multipliers.size();
        vector<vector<int>> dp(m + 1, vector<int>(m + 1, INT_MIN));
        dp[0][0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int left = 0; left <= i; left++) {
                int right = i - left;
                // 从左边取
                if (left > 0) {
                    dp[i][left] = max(dp[i][left], 
                        dp[i-1][left-1] + nums[left-1] * multipliers[i-1]);
                }
                // 从右边取
                if (right > 0) {
                    dp[i][left] = max(dp[i][left], 
                        dp[i-1][left] + nums[n-right] * multipliers[i-1]);
                }
            }
        }
        
        int result = INT_MIN;
        for (int left = 0; left <= m; left++) {
            result = max(result, dp[m][left]);
        }
        return result;
    }
};

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        n, m = len(nums), len(multipliers)
        dp = [[float('-inf')] * (m + 1) for _ in range(m + 1)]
        dp[0][0] = 0
        
        for i in range(1, m + 1):
            for left in range(i + 1):
                right = i - left
                # 从左边取
                if left > 0:
                    dp[i][left] = max(dp[i][left], 
                        dp[i-1][left-1] + nums[left-1] * multipliers[i-1])
                # 从右边取
                if right > 0:
                    dp[i][left] = max(dp[i][left], 
                        dp[i-1][left] + nums[n-right] * multipliers[i-1])
        
        return max(dp[m])

public class Solution {
    public int MaximumScore(int[] nums, int[] multipliers) {
        int n = nums.Length, m = multipliers.Length;
        int[,] dp = new int[m + 1, m + 1];
        
        // 初始化为最小值
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i, j] = int.MinValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int left = 0; left <= i; left++) {
                int right = i - left;
                // 从左边取
                if (left > 0) {
                    dp[i, left] = Math.Max(dp[i, left], 
                        dp[i-1, left-1] + nums[left-1] * multipliers[i-1]);
                }
                // 从右边取
                if (right > 0) {
                    dp[i, left] = Math.Max(dp[i, left], 
                        dp[i-1, left] + nums[n-right] * multipliers[i-1]);
                }
            }
        }
        
        int result = int.MinValue;
        for (int left = 0; left <= m; left++) {
            result = Math.Max(result, dp[m, left]);
        }
        return result;
    }
}

var maximumScore = function(nums, multipliers) {
    const n = nums.length, m = multipliers.length;
    const dp = Array(m + 1).fill(null).map(() => Array(m + 1).fill(-Infinity));
    dp[0][0] = 0;
    
    for (let i = 1; i <= m; i++) {
        for (let left = 0; left <= i; left++) {
            const right = i - left;
            // 从左边取
            if (left > 0) {
                dp[i][left] = Math.max(dp[i][left], 
                    dp[i-1][left-1] + nums[left-1] * multipliers[i-1]);
            }
            // 从右边取
            if (right > 0) {
                dp[i][left] = Math.max(dp[i][left], 
                    dp[i-1][left] + nums[n-right] * multipliers[i-1]);
            }
        }
    }
    
    return Math.max(...dp[m]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
动态规划O(m²)O(m²)
  • 时间复杂度：O(m²)，其中 m 是 multipliers 数组的长度。我们需要填充 m×m 的动态规划表。
  • 空间复杂度：O(m²)，用于存储动态规划状态。可以优化为 O(m) 使用滚动数组。

相关题目