Maximum subsequence score
May 23, 2023heap
Problem URL: Maximum subsequence score
We can use a heap to store the elements in the array. Then, we can pop the elements from the heap and add them to the result. We will also keep track of the sum of the elements in the heap. If the sum is greater than the result, we will update the result.
class Solution: def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int: res, prefixSum, maxHeap = 0, 0,  for a, b in sorted(list(zip(nums1, nums2)), key=itemgetter(1), reverse=True): prefixSum += a heappush(maxHeap, a) if len(maxHeap) == k: res = max(res, prefixSum * b) prefixSum -= heappop(maxHeap) return res
O(nlog(n)) where n is the length of the array.
O(n) where n is the length of the array.