Maximum Subsequence Score

Problem in plain words

You have two arrays nums1 and nums2 of the same length and a number k. Pick exactly k indices. The score of your pick is (the sum of the chosen nums1 values) × (the smallest of the chosen nums2 values). Return the highest score possible.

Example: nums1 = [4, 1, 3], nums2 = [1, 5, 2], k = 2. Picking indices 1 and 2 gives (1 + 3) × min(5, 2) = 8; indices 0 and 2 give (4 + 3) × 1 = 7; indices 0 and 1 give 5 × 1 = 5. The best is 8.

Intuition

Two things pull against each other: a big sum and a big minimum. Fix the minimum instead of searching for it. Sort the indices by nums2 from largest to smallest. When you reach position i and treat its nums2 value as the minimum, every earlier index has a nums2 value at least as large, so it is a legal companion. Among those, you want the k - 1 largest nums1 values (plus the current one). A min-heap of size k over nums1 maintains the k largest values seen so far and their running sum: push the new value, and if the heap grows beyond k, pop the smallest.

Approach

1. Pair up (nums2[i], nums1[i]) and sort by nums2 in descending order.
2. Walk the sorted pairs. Push nums1 onto a min-heap and add it to sum.
3. If the heap size exceeds k, pop the smallest value and subtract it from sum.
4. When the heap size equals k, update best = max(best, sum × current nums2).
5. Return best.

Dry run

Sorted pairs (nums2, nums1): (5, 1), (2, 3), (1, 4); k = 2.

Java solution

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, (a, b) -> nums2[b] - nums2[a]);

        PriorityQueue<Integer> heap = new PriorityQueue<>();
        long sum = 0;
        long best = 0;
        for (int idx : order) {
            heap.offer(nums1[idx]);
            sum += nums1[idx];
            if (heap.size() > k) {
                sum -= heap.poll();
            }
            if (heap.size() == k) {
                best = Math.max(best, sum * nums2[idx]);
            }
        }
        return best;
    }
}

Python solution

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = sorted(zip(nums2, nums1), reverse=True)
        heap, total, best = [], 0, 0
        for minimum, value in pairs:
            heapq.heappush(heap, value)
            total += value
            if len(heap) > k:
                total -= heapq.heappop(heap)
            if len(heap) == k:
                best = max(best, total * minimum)
        return best

Complexity

Edge cases and common mistakes

• Overflow — the sum can reach about 10^10 and the product about 10^15. Use long in Java.
• Scoring before the heap is full — only a group of exactly k indices is valid, so score only when the size equals k.
• What if the popped value is the current one? — then the heap's k values all have nums2 at least the current value, so sum × current underestimates a group already counted earlier. It never overestimates, so the maximum stays correct.
• k = 1 — the answer is the best single nums1[i] × nums2[i], which this loop also finds.