Welcome to Subscribe On Youtube
3836. Maximum Score Using Exactly K Pairs
Description
You are given two integer arrays nums1 and nums2 of lengths n and m respectively, and an integer k.
You must choose exactly k pairs of indices (i1, j1), (i2, j2), ..., (ik, jk) such that:
0 <= i1 < i2 < ... < ik < n0 <= j1 < j2 < ... < jk < m
For each chosen pair (i, j), you gain a score of nums1[i] * nums2[j].
The total score is the sum of the products of all selected pairs.
Return an integer representing the maximum achievable total score.
Example 1:
Input: nums1 = [1,3,2], nums2 = [4,5,1], k = 2
Output: 22
Explanation:
One optimal choice of index pairs is:
(i1, j1) = (1, 0)which scores3 * 4 = 12(i2, j2) = (2, 1)which scores2 * 5 = 10
This gives a total score of 12 + 10 = 22.
Example 2:
Input: nums1 = [-2,0,5], nums2 = [-3,4,-1,2], k = 2
Output: 26
Explanation:
One optimal choice of index pairs is:
(i1, j1) = (0, 0)which scores-2 * -3 = 6(i2, j2) = (2, 1)which scores5 * 4 = 20
The total score is 6 + 20 = 26.
Example 3:
Input: nums1 = [-3,-2], nums2 = [1,2], k = 2
Output: -7
Explanation:
The optimal choice of index pairs is:
(i1, j1) = (0, 0)which scores-3 * 1 = -3(i2, j2) = (1, 1)which scores-2 * 2 = -4
The total score is -3 + (-4) = -7.
Constraints:
1 <= n == nums1.length <= 1001 <= m == nums2.length <= 100-106 <= nums1[i], nums2[i] <= 1061 <= k <= min(n, m)
Solutions
Solution 1: Dynamic Programming
We denote the lengths of arrays $\textit{nums1}$ and $\textit{nums2}$ as $n$ and $m$ respectively, and denote $k$ in the problem as $K$.
We define a three-dimensional array $f$, where $f[i][j][k]$ represents the maximum score of selecting exactly $k$ index pairs from the first $i$ elements of $\textit{nums1}$ and the first $j$ elements of $\textit{nums2}$. Initially, $f[0][0][0] = 0$, and all other values of $f[i][j][k]$ are negative infinity.
We can calculate $f[i][j][k]$ through the following state transition equation:
\[f[i][j][k] = \max\begin{cases} f[i-1][j][k], \\ f[i][j-1][k], \\ f[i-1][j-1][k-1] + nums1[i-1] * nums2[j-1] \end{cases}\]The first case represents not selecting the $i$-th element of $\textit{nums1}$, the second case represents not selecting the $j$-th element of $\textit{nums2}$, and the third case represents selecting the $i$-th element of $\textit{nums1}$ and the $j$-th element of $\textit{nums2}$ as a pair of indices.
Finally, we need to return $f[n][m][K]$.
The time complexity is $O(m \times n \times K)$ and the space complexity is $O(m \times n \times K)$, where $n$ and $m$ are the lengths of arrays $\textit{nums1}$ and $\textit{nums2}$ respectively, and $K$ is $k$ in the problem.
-
class Solution { public long maxScore(int[] nums1, int[] nums2, int K) { int n = nums1.length, m = nums2.length; long NEG = Long.MIN_VALUE / 4; long[][][] f = new long[n + 1][m + 1][K + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { Arrays.fill(f[i][j], NEG); } } f[0][0][0] = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= K; k++) { if (i > 0) { f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j][k]); } if (j > 0) { f[i][j][k] = Math.max(f[i][j][k], f[i][j - 1][k]); } if (i > 0 && j > 0 && k > 0) { f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - 1][k - 1] + (long) nums1[i - 1] * nums2[j - 1]); } } } } return f[n][m][K]; } } -
class Solution { public: long long maxScore(vector<int>& nums1, vector<int>& nums2, int K) { int n = nums1.size(), m = nums2.size(); long long NEG = LLONG_MIN / 4; vector f(n + 1, vector(m + 1, vector<long long>(K + 1, NEG))); f[0][0][0] = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= K; k++) { if (i > 0) { f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]); } if (j > 0) { f[i][j][k] = max(f[i][j][k], f[i][j - 1][k]); } if (i > 0 && j > 0 && k > 0) { f[i][j][k] = max( f[i][j][k], f[i - 1][j - 1][k - 1] + 1LL * nums1[i - 1] * nums2[j - 1]); } } } } return f[n][m][K]; } }; -
class Solution: def maxScore(self, nums1: List[int], nums2: List[int], K: int) -> int: n, m = len(nums1), len(nums2) f = [[[-inf] * (K + 1) for _ in range(m + 1)] for _ in range(n + 1)] f[0][0][0] = 0 for i in range(n + 1): for j in range(m + 1): for k in range(K + 1): if i > 0: f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]) if j > 0: f[i][j][k] = max(f[i][j][k], f[i][j - 1][k]) if i > 0 and j > 0 and k > 0: f[i][j][k] = max( f[i][j][k], f[i - 1][j - 1][k - 1] + nums1[i - 1] * nums2[j - 1], ) return f[n][m][K] -
func maxScore(nums1 []int, nums2 []int, K int) int64 { n, m := len(nums1), len(nums2) NEG := int64(math.MinInt64 / 4) f := make([][][]int64, n+1) for i := 0; i <= n; i++ { f[i] = make([][]int64, m+1) for j := 0; j <= m; j++ { f[i][j] = make([]int64, K+1) for k := 0; k <= K; k++ { f[i][j][k] = NEG } } } f[0][0][0] = 0 for i := 0; i <= n; i++ { for j := 0; j <= m; j++ { for k := 0; k <= K; k++ { if i > 0 { f[i][j][k] = max(f[i][j][k], f[i-1][j][k]) } if j > 0 { f[i][j][k] = max(f[i][j][k], f[i][j-1][k]) } if i > 0 && j > 0 && k > 0 { f[i][j][k] = max( f[i][j][k], f[i-1][j-1][k-1]+int64(nums1[i-1])*int64(nums2[j-1]), ) } } } } return f[n][m][K] } -
function maxScore(nums1: number[], nums2: number[], K: number): number { const n = nums1.length, m = nums2.length; const NEG = -1e18; const f = Array.from({ length: n + 1 }, () => Array.from({ length: m + 1 }, () => Array(K + 1).fill(NEG)), ); f[0][0][0] = 0; for (let i = 0; i <= n; i++) { for (let j = 0; j <= m; j++) { for (let k = 0; k <= K; k++) { if (i > 0) { f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j][k]); } if (j > 0) { f[i][j][k] = Math.max(f[i][j][k], f[i][j - 1][k]); } if (i > 0 && j > 0 && k > 0) { f[i][j][k] = Math.max( f[i][j][k], f[i - 1][j - 1][k - 1] + nums1[i - 1] * nums2[j - 1], ); } } } } return f[n][m][K]; }