2542.Maximum Subsequence Score

Problem Statement

link: LeetCode.cn LeetCode 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

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1 Output: 30

Solution Approach

To maximize the subsequence score, we sort pairs of elements from nums1 and nums2 by nums2 in descending order, use a heap to track the top k elements from nums1, and dynamically calculate the sum and the product with the current minimum of nums2 values.

Algorithm

1. Sorting: Sort pairs of elements from nums1 and nums2 by the values of nums2 in descending order to prioritize larger multipliers.
2. Heap Management: Use a min-heap to maintain the top k elements from nums1 for efficient retrieval and updates as we iterate through the sorted pairs.
3. Dynamic Calculation: Continuously calculate the subsequence sum from the heap and update the maximum possible score by multiplying this sum with the current minimum value from nums2 as we process each pair.

Implement

    class Solution:
        def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
            # a = sorted(zip(nums1, nums2), key = lambda p: -p[1])
            # h = [x for x, _ in a[:k]]
            # heapify(h)
            # s = sum(h)
            # ans = s * a[k - 1][1]
            # for x, y in a[k:]:
            #     if x > h[0]:
            #         s += x - heapreplace(h, x)
            #         ans = max(ans, s * y)
            # return ans
            a = sorted(zip(nums1, nums2), key=lambda p: -p[1])
            h = [x for x, _ in a[:k]]
            heapify(h)
            s = sum(h)
            ans = s * a[k - 1][1]
            
            for x, y in a[k:]:
                if x > h[0]:
                    s += x - heappop(h)
                    heappush(h, x)
                    ans = max(ans, s * y)
            
            return ans

    
    

Twitter  facebook  Email