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.

Example 1

Input: nums1=[1,3,3,2], nums2=[2,1,3,4], k=3 → Output: 12

Example 2

Input: nums1=[4,2,3,1,1], nums2=[7,5,10,9,6], k=5 → Output: 30

Solution Approach

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].

Java

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)