Maximum Subsequence Score
Medium · Heap & Counting · Array · Greedy · Sorting · Heap (Priority Queue)
Problem
You are given two arrays nums1 and nums2 of equal length n, and an integer k.
Choose exactly k indices. The score of the choice is the sum of the chosen nums1 values multiplied by the minimum of the chosen nums2 values.
Return the largest possible score.
Examples
Input: nums1 = [2,1,3,4], nums2 = [5,2,4,1], k = 2 Output: 20
Indices 0 and 2 give (2 + 3) x min(5, 4) = 20. Adding index 3 instead would raise the sum but drop the minimum to 1.
Input: nums1 = [1,2], nums2 = [3,3], k = 1 Output: 6
Index 1 alone: 2 x 3 = 6.
Constraints
- n == len(nums1) == len(nums2)
- 1 <= n <= 10^5
- 0 <= nums1[i], nums2[i] <= 10^5
- 1 <= k <= n
Approaches
- Try each index as the minimum — time O(n² log n), space O(n)
Follow-up
What if you may choose any number of indices from 1 to k instead of exactly k? Then every step of the same sweep is a candidate, even before the heap is full, and the heap still drops its smallest value once it holds more than k.
Related problems
Start free on Cariara · Coding problems · System design studio
