Maximum Subsequence Score

Problem Description

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. For chosen indices i_0, i_1, ..., i_{k - 1}, your score is defined as the sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2. Return the maximum possible score.

Key Insights

• The problem involves selecting a subsequence of length k from nums1.
• The score is calculated by summing the selected elements from nums1 and multiplying by the minimum value from the corresponding indices in nums2.
• A greedy approach can be employed to maximize the score by selecting the largest elements from nums1 while ensuring that the minimum value from nums2 is maximized.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a greedy algorithm combined with a heap (priority queue). The steps are as follows:

1. Pair each element in nums1 with its corresponding element in nums2.
2. Sort the pairs based on the values in nums2 in descending order. This ensures that we can always consider the largest minimum values first.
3. Use a min-heap to keep track of the largest k elements from nums1 as we iterate through the sorted pairs.
4. For each element, if the heap size exceeds k, remove the smallest element (to maintain the size).
5. Calculate the score using the sum of the elements in the heap multiplied by the current nums2 value.
6. Keep track of the maximum score encountered.

This approach effectively finds the optimal subsequence while ensuring the minimum of nums2 is as high as possible.

Code Solutions