3290. Maximum Multiplication Score LeetCode Solution
In this guide, you will get 3290. Maximum Multiplication Score LeetCode Solution with the best time and space complexity. The solution to Maximum Multiplication Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given an integer array a of size 4 and another integer array b of size at least 4.
You need to choose 4 indices i0, i1, i2, and i3 from the array b such that i0 < i1 < i2 < i3. Your score will be equal to the value a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3].
Return the maximum score you can achieve.
Example 1:
Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
Output: 26
Explanation:
We can choose the indices 0, 1, 2, and 5. The score will be 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26.
Example 2:
Input: a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]
Output: -1
Explanation:
We can choose the indices 0, 1, 3, and 4. The score will be (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1.
Time Complexity: O(4 \cdot |\texttt{b}|) = O(|\texttt{b}|)
Space Complexity: O(4 \cdot |\texttt{b}|) = O(|\texttt{b}|)
3290. Maximum Multiplication Score LeetCode Solution in C++
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];
}
}; /* code provided by PROGIEZ */
3290. Maximum Multiplication Score LeetCode Solution in Java
class Solution {
public long maxScore(int[] a, int[] b) {
final int n = b.length;
final long kMin = 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] = 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] = Math.max(dp[i][j + 1], a[i] * (long) b[j] + dp[i + 1][j + 1]);
return dp[0][0] == kMin ? -1 : dp[0][0];
}
} // code provided by PROGIEZ
3290. Maximum Multiplication Score LeetCode Solution in Python
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] # code by PROGIEZ
