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 < mFor 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 scores 3 * 4 = 12(i2, j2) = (2, 1) which scores 2 * 5 = 10This 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 scores 5 * 4 = 20The 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 = -4The 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 for this problem are being prepared.
Try solving it yourselfPractice Maximum Score Using Exactly K Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor