Maximum Subsequence Score solution and explanation

import heapq

def maxScore(nums1, nums2, k):
    pairs = sorted(zip(nums2, nums1), reverse=True)
    min_heap = []
    current_sum = 0
    max_score = 0
    for num2, num1 in pairs:
        heapq.heappush(min_heap, num1)
        current_sum += num1
        if len(min_heap) > k:
            current_sum -= heapq.heappop(min_heap)
        if len(min_heap) == k:
            max_score = max(max_score, current_sum * num2)
    return max_score

# Example usage
print(maxScore([1,3,3,2], [2,1,3,4], 3))  # Output: 12

#include <vector>
#include <queue>
#include <algorithm>

int maxScore(std::vector<int>& nums1, std::vector<int>& nums2, int k) {
    std::vector<std::pair<int, int>> pairs;
    for (size_t i = 0; i < nums1.size(); ++i) {
        pairs.emplace_back(nums2[i], nums1[i]);
    }
    std::sort(pairs.rbegin(), pairs.rend());
    std::priority_queue<int, std::vector<int>, std::greater<>> min_heap;
    long long current_sum = 0, max_score = 0;
    for (const auto& [num2, num1] : pairs) {
        min_heap.push(num1);
        current_sum += num1;
        if (min_heap.size() > k) {
            current_sum -= min_heap.top();
            min_heap.pop();
        }
        if (min_heap.size() == k) {
            max_score = std::max(max_score, current_sum * num2);
        }
    }
    return max_score;
}

// Example usage
// std::cout << maxScore({1,3,3,2}, {2,1,3,4}, 3) << std::endl;  // Output: 12

import java.util.*;

public class Solution {
    public int maxScore(int[] nums1, int[] nums2, int k) {
        List<int[]> pairs = new ArrayList<>();
        for (int i = 0; i < nums1.length; ++i) {
            pairs.add(new int[]{nums2[i], nums1[i]});
        }
        pairs.sort((a, b) -> Integer.compare(b[0], a[0]));

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        long currentSum = 0, maxScore = 0;
        for (int[] pair : pairs) {
            int num2 = pair[0], num1 = pair[1];
            minHeap.add(num1);
            currentSum += num1;
            if (minHeap.size() > k) {
                currentSum -= minHeap.poll();
            }
            if (minHeap.size() == k) {
                maxScore = Math.max(maxScore, currentSum * num2);
            }
        }
        return (int) maxScore;
    }

    // Example usage
    // public static void main(String[] args) {
    //     System.out.println(new Solution().maxScore(new int[]{1,3,3,2}, new int[]{2,1,3,4}, 3));  // Output: 12
    // }
}

function maxScore(nums1, nums2, k) {
    const pairs = nums1.map((num1, i) => [nums2[i], num1]).sort((a, b) => b[0] - a[0]);
    const minHeap = [];
    let currentSum = 0, maxScore = 0;

    for (let [num2, num1] of pairs) {
        minHeap.push(num1);
        currentSum += num1;
        if (minHeap.length > k) {
            currentSum -= Math.min(...minHeap);
            minHeap.splice(minHeap.indexOf(Math.min(...minHeap)), 1);
        }
        if (minHeap.length === k) {
            maxScore = Math.max(maxScore, currentSum * num2);
        }
    }

    return maxScore;
}

// Example usage
// console.log(maxScore([1,3,3,2], [2,1,3,4], 3));  // Output: 12

func maxScore(nums1 []int, nums2 []int, k int) int64 {
	type pair struct{ a, b int }
	nums := []pair{}
	for i, a := range nums1 {
		b := nums2[i]
		nums = append(nums, pair{a, b})
	}
	sort.Slice(nums, func(i, j int) bool { return nums[i].b > nums[j].b })
	q := hp{}
	var ans, s int
	for _, e := range nums {
		a, b := e.a, e.b
		s += a
		heap.Push(&q, a)
		if q.Len() == k {
			ans = max(ans, s*b)
			s -= heap.Pop(&q).(int)
		}
	}
	return int64(ans)
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}