2542

2542. Maximum Subsequence Score (Medium)

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 i0, i1, ..., ik - 1, your score is defined as:

• The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
• It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).

Return the maximum possible score.

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.

 

Example 1:

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation: 
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

Example 2:

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation: 
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

 

Constraints:

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 0 <= nums1[i], nums2[j] <= 105
• 1 <= k <= n

Companies: Amazon, Adobe, DE Shaw

Related Topics:
Array, Greedy, Sorting, Heap (Priority Queue)

Similar Questions:

• IPO (Hard)
• Minimum Cost to Hire K Workers (Hard)

Hints:

• How can we use sorting here?
• Try sorting the two arrays based on second array.
• Loop through nums2 and compute the max product given the minimum is nums2[i]. Update the answer accordingly.

Solution 1. Sorting + Heap

Intuition: If we sort B and traverse B in a specific order, we can easily know the minimum value. The next thing we need to figure out is the maximum k elements in A.

Algorithm:

Zip A and B into an array C such that C[i] = (A[i], B[i]). Sort C in descending order of the 2nd dimension, i.e. B values.

Traverse C from left to right. The last seen B value is the minimum value. To track the top K elements, we use a min heap. Whenever we visit a new C[i], we push its A value into the heap, and add this value to sum. When heap has more than K elements, we pop the top, and remove this top value from sum. In this way, we keep track of the sum of the top K elements.

// OJ: https://leetcode.com/problems/maximum-subsequence-score
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    long long maxScore(vector<int>& A, vector<int>& B, int k) {
        vector<pair<int, int>> C;
        long long N = A.size(), sum = 0, ans = 0;
        for (int i = 0; i < N; ++i) C.emplace_back(A[i], B[i]);
        sort(begin(C), end(C), [](auto &a, auto &b) { return a.second > b.second; });
        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 0; i < N; ++i) {
            auto &[a, b] = C[i];
            pq.push(a);
            sum += a;
            if (pq.size() > k) {
                sum -= pq.top();
                pq.pop();
            }
            if (i >= k - 1) ans = max(ans, b * sum);
        }
        return ans;
    }
};