3836. Maximum Score Using Exactly K Pairs Hard

1/**
2 * [3836] Maximum Score Using Exactly K Pairs
3 *
4 * You are given two integer arrays nums1 and nums2 of lengths n and m respectively, and an integer k.
5 * You must choose exactly k pairs of indices (i1, j1), (i2, j2), ..., (ik, jk) such that:
6 * 
7 * 	0 <= i1 < i2 < ... < ik < n
8 * 	0 <= j1 < j2 < ... < jk < m
9 * 
10 * For each chosen pair (i, j), you gain a score of nums1[i] * nums2[j].
11 * The total score is the sum of the products of all selected pairs.
12 * Return an integer representing the maximum achievable total score.
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">nums1 = [1,3,2], nums2 = [4,5,1], k = 2</span>
17 * Output: <span class="example-io">22</span>
18 * Explanation:
19 * One optimal choice of index pairs is:
20 * 
21 * 	(i1, j1) = (1, 0) which scores 3 * 4 = 12
22 * 	(i2, j2) = (2, 1) which scores 2 * 5 = 10
23 * 
24 * This gives a total score of 12 + 10 = 22.
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">nums1 = [-2,0,5], nums2 = [-3,4,-1,2], k = 2</span>
29 * Output: <span class="example-io">26</span>
30 * Explanation:
31 * One optimal choice of index pairs is:
32 * 
33 * 	(i1, j1) = (0, 0) which scores -2 * -3 = 6
34 * 	(i2, j2) = (2, 1) which scores 5 * 4 = 20
35 * 
36 * The total score is 6 + 20 = 26.
37 * </div>
38 * <strong class="example">Example 3:
39 * <div class="example-block">
40 * Input: <span class="example-io">nums1 = [-3,-2], nums2 = [1,2], k = 2</span>
41 * Output: <span class="example-io">-7</span>
42 * Explanation:
43 * The optimal choice of index pairs is:
44 * 
45 * 	(i1, j1) = (0, 0) which scores -3 * 1 = -3
46 * 	(i2, j2) = (1, 1) which scores -2 * 2 = -4
47 * 
48 * The total score is -3 + (-4) = -7.
49 * </div>
50 *  
51 * Constraints:
52 * 
53 * 	1 <= n == nums1.length <= 100
54 * 	1 <= m == nums2.length <= 100
55 * 	-10^6 <= nums1[i], nums2[i] <= 10^6
56 * 	1 <= k <= min(n, m)
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/maximum-score-using-exactly-k-pairs/
62// discuss: https://leetcode.com/problems/maximum-score-using-exactly-k-pairs/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn max_score(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
68        
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_3836() {
80    }
81}
82