670. Maximum Subsequence Score
You are given two integer arrays nums1 and nums2, both of length n, and an integer k. Pick exactly k distinct indices i₁, …, iₖ. The score of a pick is
(nums1[i₁] + … + nums1[iₖ]) × min(nums2[i₁], …, nums2[iₖ])
— the sum of the chosen nums1 values, multiplied by the smallest of the chosen nums2 values.
Return the largest score any pick of k indices can achieve.
Example 1:
Input: nums1 = [2, 1, 4, 3], nums2 = [3, 5, 2, 4], k = 2
Output: 16
Explanation: Indices {1, 3} give (1 + 3) × min(5, 4) = 4 × 4 = 16. No other pair beats it: {0, 3} gives (2 + 3) × 3 = 15, and {2, 3} gives (4 + 3) × 2 = 14.
Example 2:
Input: nums1 = [4, 2, 3], nums2 = [1, 7, 5], k = 1
Output: 15
Explanation: With k = 1 the score of index i is just nums1[i] × nums2[i]: 4, 14, and 15. Index 2 wins with 3 × 5 = 15.
Constraints:
- 1 ≤ n ≤ 10⁵, where n == nums1.length == nums2.length
- 0 ≤ nums1[i], nums2[i] ≤ 10⁵
- 1 ≤ k ≤ n
Hints:
Every chosen set has one element whose nums2 value is the minimum. What if you committed to that anchor first — which k − 1 companions would you then want beside it?
Sort the index pairs by nums2 descending and sweep. Standing at pair i, everything already processed has nums2 >= nums2[i], so nums2[i] is the multiplier if i is included; the best companions are the largest nums1 values seen so far. Maintain them with a size-k min-heap and a running sum, recording sum × nums2[i] whenever the heap is full.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [2, 1, 4, 3], nums2 = [3, 5, 2, 4], k = 2
Expected output: 16