[LeetCode] Maximum Subsequence Score

Problem: 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:

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.

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

Apporach: The intuition here is to select the k indices that would result in the largest possible sum from nums1 while also ensuring that the minimum value selected from nums2 is as high as possible, because it multiplies the entire sum and we also need to take care these indices might not be coniguous.

How we can do that? If we sort the nums2 array in descending order then we know that maximum possible minimum value is if we include nums2[0.....k] is going to be nums2[k] in the sorted nums2. Now that we have identified how to get the min value from nums2. We need to figure out how to get the sum of those elements from the nums1 which corresponds to the same indices which we are using in nums2 to get the min value.

That means we can't independently sort nums2. What we can do is we can make pair(num1[i], nums2[i]) and sort these list of pairs in the desending order of nums2[i].

Now things become simple for us. We iterate through the list of pairs we created. Given we need to increase the sum as much as possible. We can maintain a heap/priority queue to store k elements of nums1 from the sorted pairs. We keep adding these values as current_sum. When we get more than k elements, we simply calculate current_score as current_sum * pair(nums2[i]) as we know that the current value of nums2 in current pair will be minimum given it is sorted in descending order. Now we can remove the smallest element from the heap safely as we want to get the maximum sum right.

In the end we can retrun the maximum of all the scores we calculated.

That's all!

Implementation in C#:

    public long MaxScore(int[] nums1, int[] nums2, int k)

    {

        int length = nums1?.Length ?? 0;

        if (length < k)

        {

            return -1;

        }

        var pairs = this.CreateSortedPairs(nums1, nums2);

        var pq = new PriorityQueue<int, int>();

        long currSum = 0, maxScore = 0;

        for (int i = 0; i < length; ++i)

        {

            currSum += pairs[i][0];

            pq.Enqueue(pairs[i][0], pairs[i][0]);

            if (pq.Count == k)

            {

                long currScore = currSum * pairs[i][1];

                maxScore = Math.Max(maxScore, currScore);

                currSum -= pq.Dequeue();

            }

        }

        return maxScore;

    }

    private int[][] CreateSortedPairs(int[] nums1, int[] nums2)

    {

        int length = nums1.Length;

        var pairs = new int[length][];

        for (int i = 0; i < length; ++i)

        {

            pairs[i] = new int[2];

            pairs[i][0] = nums1[i];

            pairs[i][1] = nums2[i];

        }

        Array.Sort(pairs, (p1, p2) => {

            return p2[1].CompareTo(p1[1]);

        });

        return pairs;

    }

Complexity: O(nlogn) + O(nlogk)