2542

1. 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.
It can defined simply as: (nums1[$i_0$] + nums1[$i_1$] +…+ nums1[$i_k$ - 1]) * min(nums2[$i_0$] , nums2[$i_1$], … ,nums2[$i_k$ - 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.

2. Example

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.

3. Constraints

n == nums1.length == nums2.length
1 <= n <= $10^5$
0 <= nums1[i], nums2[j] <= $10^5$
1 <= k <= n

4. Solutions

Greedy && Heap

n = nums1.size()
Time complexity: O(nlogn)
Space complexity: O(n)

// Our goal is to maximize the score: (sum of selected elements) * (minimum value).
// We sort the elements by value in descending order, and treat the current value
// as the minimum (bottleneck) in the selection.
// For each value, we maintain the maximum possible sum of k elements using a heap.
// To simplify the process, we pair the values and sort them together.

class Solution {
public:
    long long maxScore(vector<int> &nums1, vector<int> &nums2, int k) {
        vector<pair<int, int>> nums;
        nums.reserve(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            nums.emplace_back(nums1[i], nums2[i]);
        }

        sort(nums.begin(), nums.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
            return a.second > b.second;
        });

        priority_queue<int, vector<int>, greater<int>> top_k_values;
        long long sum = 0;
        for (int i = 0; i < k; ++i) {
            top_k_values.push(nums[i].first);
            sum += nums[i].first;
        }
        long long max_score = sum * nums[k - 1].second;

        for (int i = k; i < nums.size(); ++i) {
            int min_value = top_k_values.top();
            top_k_values.pop();
            top_k_values.push(nums[i].first);

            sum = sum - min_value + nums[i].first;
            max_score = max(sum * nums[i].second, max_score);
        }

        return max_score;
    }
};

Search

Tags