Medium

题目描述

给你一个大小为 4 的整数数组 a 和另一个大小至少为 4 的整数数组 b。

你需要从数组 b 中选择 4 个下标 i0、i1、i2 和 i3，使得 i0 < i1 < i2 < i3。你的分数等于 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]。

返回你能达到的最大分数。

示例 1：

输入：a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
输出：26
解释：我们可以选择下标 0, 1, 2, 5。分数为 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26。

示例 2：

输入：a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]
输出：-1
解释：我们可以选择下标 0, 1, 3, 4。分数为 (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1。

提示：

  • a.length == 4
  • 4 <= b.length <= 10^5
  • -10^5 <= a[i], b[i] <= 10^5

解题思路

这是一个典型的动态规划问题。核心思想是从数组 b 中按顺序选择 4 个元素，与数组 a 的 4 个元素分别相乘求和，目标是最大化总分数。

解题思路

状态定义： 设 dp[i][j] 表示考虑数组 b 的前 i 个元素，已经选择了 j 个元素时能获得的最大分数。

状态转移： 对于每个位置 i 和已选择数量 j，我们有两种选择：

  1. 不选择当前元素：dp[i][j] = dp[i-1][j]
  2. 选择当前元素：dp[i][j] = dp[i-1][j-1] + a[j-1] * b[i-1]

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

边界条件：

  • dp[0][0] = 0（没选择任何元素时分数为 0）
  • dp[i][j] = -∞（当 j > i 或其他无效状态时）

优化思路： 由于只需要前一行的状态，可以使用滚动数组优化空间复杂度到 O(1)。但考虑到 j 最大为 4，直接使用二维数组也很高效。

最终答案为 dp[n][4]，其中 n 是数组 b 的长度。

代码实现

class Solution {
public:
    long long maxScore(vector<int>& a, vector<int>& b) {
        int n = b.size();
        vector<vector<long long>> dp(n + 1, vector<long long>(5, LLONG_MIN));
        
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= min(4, i); j++) {
                dp[i][j] = dp[i-1][j];
                if (j > 0 && dp[i-1][j-1] != LLONG_MIN) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + (long long)a[j-1] * b[i-1]);
                }
            }
        }
        
        return dp[n][4];
    }
};

class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        n = len(b)
        dp = [[-float('inf')] * 5 for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for j in range(min(4, i) + 1):
                dp[i][j] = dp[i-1][j]
                if j > 0 and dp[i-1][j-1] != -float('inf'):
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + a[j-1] * b[i-1])
        
        return dp[n][4]

public class Solution {
    public long MaxScore(int[] a, int[] b) {
        int n = b.Length;
        long[,] dp = new long[n + 1, 5];
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= 4; j++) {
                dp[i, j] = long.MinValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= Math.Min(4, i); j++) {
                dp[i, j] = dp[i - 1, j];
                if (j > 0 && dp[i - 1, j - 1] != long.MinValue) {
                    dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j - 1] + (long)a[j - 1] * b[i - 1]);
                }
            }
        }
        
        return dp[n, 4];
    }
}

var maxScore = function(a, b) {
    const n = b.length;
    const dp = Array(n + 1).fill().map(() => Array(5).fill(-Infinity));
    dp[0][0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= Math.min(4, i); j++) {
            dp[i][j] = dp[i-1][j];
            if (j > 0 && dp[i-1][j-1] !== -Infinity) {
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + a[j-1] * b[i-1]);
            }
        }
    }
    
    return dp[n][4];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)其中 n 是数组 b 的长度，内层循环最多 5 次，可视为常数
空间复杂度O(n)需要 (n+1) × 5 的二维数组存储状态