Skip to content

3290. Maximum Multiplication Score 👍

Approach 1: 2D DP

  • Time: $O(4 \cdot |\texttt{b}|) = O(|\texttt{b}|)$
  • Space: $O(4 \cdot |\texttt{b}|) = O(|\texttt{b}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  long long maxScore(vector<int>& a, vector<int>& b) {
    const int n = b.size();
    const long kMin = LONG_MIN / 2;
    // dp[i][j] := the maximum score by selecting 4 - i numbers from b[j..n - 1]
    // using the corresponding numbers from a[i..3]
    vector<vector<long>> dp(5, vector<long>(n + 1));

    // Run out of numbers in b but still need to select numbers from a.
    for (int i = 0; i < 4; ++i)
      dp[i][n] = kMin;

    for (int i = 3; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        // Skip b[j] or pair a[i] with b[j].
        dp[i][j] = max(dp[i][j + 1],
                       a[i] * static_cast<long>(b[j]) + dp[i + 1][j + 1]);

    return dp[0][0] == kMin ? -1 : dp[0][0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public long maxScore(int[] a, int[] b) {
    final int n = b.length;
    final long MIN = Long.MIN_VALUE / 2;
    // dp[i][j] := the maximum score by selecting 4 - i numbers from b[j..n - 1]
    // using the corresponding numbers from a[i..3]
    long[][] dp = new long[5][n + 1];

    // Run out of numbers in b but still need to select numbers from a.
    for (int i = 0; i < 4; ++i)
      dp[i][n] = MIN;

    for (int i = 3; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        // Skip b[j] or pair a[i] with b[j].
        dp[i][j] = Math.max(dp[i][j + 1], a[i] * (long) b[j] + dp[i + 1][j + 1]);

    return dp[0][0] == MIN ? -1 : dp[0][0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maxScore(self, a: list[int], b: list[int]) -> int:
    n = len(b)
    # dp[i][j] := the maximum score by selecting 4 - i numbers from b[j..n - 1]
    # using the corresponding numbers from a[i..3]
    dp = [[0] * (n + 1) for _ in range(5)]

    # Run out of numbers in b but still need to select numbers from a.
    for i in range(4):
      dp[i][n] = -math.inf

    for i in reversed(range(4)):
      for j in reversed(range(n)):
        # Skip b[j] or pair a[i] with b[j].
        dp[i][j] = max(dp[i][j + 1], a[i] * b[j] + dp[i + 1][j + 1])

    return -1 if dp[0][0] == -math.inf else dp[0][0]

Approach 2: 1D DP

  • Time: $O(4 \cdot |\texttt{b}|) = O(|\texttt{b}|)$
  • Space: $O(4) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  long long maxScore(vector<int>& a, vector<int>& b) {
    // dp[i] := the maximum score of a[0..i]
    vector<long> dp(4, LONG_MIN / 2);

    for (const long num : b)
      for (int i = 3; i >= 0; --i)
        // Skip `num` or pair a[i] with `num`.
        dp[i] = max(dp[i], (i > 0 ? dp[i - 1] : 0) + a[i] * num);

    return dp[3];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public long maxScore(int[] a, int[] b) {
    // dp[i] := the maximum score of a[0..i]
    long[] dp = new long[4];
    Arrays.fill(dp, Long.MIN_VALUE / 2);

    for (final long num : b)
      for (int i = 3; i >= 0; --i)
        // Skip `num` or pair a[i] with `num`.
        dp[i] = Math.max(dp[i], (i > 0 ? dp[i - 1] : 0) + a[i] * num);

    return dp[3];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def maxScore(self, a: list[int], b: list[int]) -> int:
    # dp[i] := the maximum score of a[0..i]
    dp = [-math.inf] * 4

    for num in b:
      for i in reversed(range(4)):
        # Skip `num` or pair a[i] with `num`.
        dp[i] = max(dp[i], (dp[i - 1] if i > 0 else 0) + a[i] * num)

    return dp[3]