Heap / Priority Queue - Maximum Subsequence Score

Given two integer arrays nums1 and nums2 of equal length n, and integer k, pick k indices where the score = sum(nums1[selected]) * min(nums2[selected]) is maximized.

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=5 → Output: 30

Sort pairs by nums2 descending. Iterate and maintain a min-heap of size k for nums1 values. At each step the minimum of nums2 is current nums2[i]; multiply by sum of top-k nums1 values.

Create pairs (nums1[i], nums2[i]), sort by nums2 descending.
Min-heap of size k for nums1 values, maintain running sum.
For each pair: add nums1 to heap and sum; if heap.size() > k, remove min from sum and heap.
When heap.size() == k: update answer with sum * nums2[i].

import java.util.*; class Solution { public long maxScore(int[] nums1, int[] nums2, int k) { int n = nums1.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> nums2[b] - nums2[a]); PriorityQueue<Integer> minHeap = new PriorityQueue<>(); long sum = 0, ans = 0; for (int i : idx) { minHeap.offer(nums1[i]); sum += nums1[i]; if (minHeap.size() > k) sum -= minHeap.poll(); if (minHeap.size() == k) ans = Math.max(ans, sum * nums2[i]); } return ans; } }

Time Complexity: O(N log N + N log k)
Space Complexity: O(N + k)