2542. Maximum Subsequence Score Medium

1/**
2 * [2542] Maximum Subsequence Score
3 *
4 * You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.
5 * For chosen indices i0, i1, ..., ik - 1, your score is defined as:
6 * 
7 * 	The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
8 * 	It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).
9 * 
10 * Return the maximum possible score.
11 * A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
16 * Output: 12
17 * Explanation: 
18 * The four possible subsequence scores are:
19 * - We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
20 * - We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
21 * - We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
22 * - We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
23 * Therefore, we return the max score, which is 12.
24 * 
25 * <strong class="example">Example 2:
26 * 
27 * Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
28 * Output: 30
29 * Explanation: 
30 * Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	n == nums1.length == nums2.length
36 * 	1 <= n <= 10^5
37 * 	0 <= nums1[i], nums2[j] <= 10^5
38 * 	1 <= k <= n
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/maximum-subsequence-score/
44// discuss: https://leetcode.com/problems/maximum-subsequence-score/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn max_score(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
50        
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_2542() {
62    }
63}
64