2542. Maximum Subsequence Score

[fockspaces]

incredibly hard problem ...

Use : Greedy + heap_q since we want the maximun value of sum(a, b, c) * min(a', b', c') we can first figure out a sorted order that can help us to keep tracking the max possible combination. then we only care about value of nums1, since nums2 is in descending order, means that nums2 will constantly update the min value for each iteration

1. sorted the list of tuple of (nums1, nums2)
2. create a heap that store the first k elements, then calculate current score
3. maintain n1_sum and n2_min, loop through the pairs
4. each time we pop the heap (the min value of n1 node), and push the new element into heap
5. keep updating the n1_sum by n1_sum = n1_sum - n1_pop + new_n1, and update the max_score
6. return max_score

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = [(n1, n2) for n1, n2 in zip(nums1, nums2)]
        sorted_pairs = sorted(pairs, key=lambda p: p[1], reverse=True)
        min_heap = [n1 for n1, _ in sorted_pairs[:k]]
        heapify(min_heap)
        n1_sum, (_, n2_min) = sum(min_heap), sorted_pairs[k - 1]
        max_score = n1_sum * n2_min
        for new_n1, n2_min in sorted_pairs[k:]:
            n1_pop = heappop(min_heap)
            heappush(min_heap, new_n1)
            n1_sum = n1_sum - n1_pop + new_n1
            max_score = max(max_score, n1_sum * n2_min)
        return max_score

https://www.youtube.com/watch?v=ax1DKi5lJwk&ab_channel=NeetCodeIO

[fockspaces]

The hard part is to figure out the CHOICES direction why can't sort by nums1 from max to min and take the order?

since we want to find the next element to update min_value if it comes to new_n1 for updating, the k elements in nums2 is not neccessary related since the min value might be any of them.

so we need to keep track the losing num_1 in each iteration for updating n1_sum