Maximum Subsequence Score
The key idea
Sort the index pairs by
nums2 descending. Then as you scan, the current pair always carries the smallest nums2 seen so far, so it fixes the minimum factor for free — leaving you to greedily keep the k largest nums1 values via a min-heap.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, ..., i(k-1), your score is defined as the sum of the selected nums1 elements multiplied by the minimum of the selected nums2 elements: (nums1[i0] + nums1[i1] + ... + nums1[i(k-1)]) * min(nums2[i0], nums2[i1], ..., nums2[i(k-1)]). Return the maximum possible score over all subsequences of indices of length k. A subsequence is a set of indices that can be derived by deleting some or no elements without changing the order of the remaining elements.
Constraints
n == nums1.length == nums2.length1 <= n <= 10^50 <= nums1[i], nums2[j] <= 10^51 <= k <= n
Examples
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
Complexity
Time: O(n log n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM