Maximum Subsequence Score

Problem

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i0, i1, ..., ik - 1, your score is defined as:

• The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
• It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.

Examples

Examples

Example 1

Input:
nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output:
 12
Explanation: 
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

#### Example 2

```d

```clike
Input:
nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output:
 30
Explanation: 
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Solution

Method 1 – Greedy with Min-Heap

Intuition

To maximize the score, we want to select k pairs such that the sum of nums1 is as large as possible, and the minimum of nums2 among those pairs is also as large as possible. By sorting pairs by nums2 in descending order and maintaining the largest k values from nums1 using a min-heap, we can efficiently compute the best score.

Approach

1. Pair up elements from nums1 and nums2 as (nums1[i], nums2[i]).
2. Sort pairs by nums2 in descending order.
3. Use a min-heap to keep track of the largest k values from nums1 as we iterate.
4. For each pair, add nums1 to the heap and sum, and if the heap size exceeds k, remove the smallest.
5. When the heap size is exactly k, calculate the score as sum * nums2 and update the maximum.
6. Return the maximum score found.

Complexity

• ⏰ Time complexity: O(n log n) — Sorting and heap operations.
• 🧺 Space complexity: O(k) — For the heap.

Code

C++

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size();
        vector<pair<int,int>> arr(n);
        for (int i = 0; i < n; ++i) arr[i] = {nums2[i], nums1[i]};
        sort(arr.rbegin(), arr.rend());
        priority_queue<int, vector<int>, greater<int>> pq;
        long long sum = 0, ans = 0;
        for (auto& [b, a] : arr) {
            pq.push(a);
            sum += a;
            if (pq.size() > k) {
                sum -= pq.top();
                pq.pop();
            }
            if (pq.size() == k) ans = max(ans, sum * b);
        }
        return ans;
    }
};

Go

func maxScore(nums1, nums2 []int, k int) int64 {
    n := len(nums1)
    arr := make([][2]int, n)
    for i := range nums1 {
        arr[i] = [2]int{nums2[i], nums1[i]}
    }
    sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] })
    pq := &IntHeap{}
    heap.Init(pq)
    sum, ans := 0, int64(0)
    for _, p := range arr {
        heap.Push(pq, p[1])
        sum += p[1]
        if pq.Len() > k {
            sum -= heap.Pop(pq).(int)
        }
        if pq.Len() == k {
            score := int64(sum) * int64(p[0])
            if score > ans { ans = score }
        }
    }
    return ans
}
// type IntHeap and heap interface implementation required

Java

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

Kotlin

class Solution {
    fun maxScore(nums1: IntArray, nums2: IntArray, k: Int): Long {
        val n = nums1.size
        val arr = Array(n) { i -> nums2[i] to nums1[i] }
        arr.sortByDescending { it.first }
        val pq = java.util.PriorityQueue<Int>()
        var sum = 0L
        var ans = 0L
        for ((b, a) in arr) {
            pq.add(a)
            sum += a
            if (pq.size > k) sum -= pq.poll()
            if (pq.size == k) ans = maxOf(ans, sum * b)
        }
        return ans
    }
}

Python

def max_score(nums1: list[int], nums2: list[int], k: int) -> int:
    import heapq
    arr = sorted(zip(nums2, nums1), reverse=True)
    pq: list[int] = []
    sum_ = 0
    ans = 0
    for b, a in arr:
        heapq.heappush(pq, a)
        sum_ += a
        if len(pq) > k:
            sum_ -= heapq.heappop(pq)
        if len(pq) == k:
            ans = max(ans, sum_ * b)
    return ans

Rust

impl Solution {
    pub fn max_score(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
        let n = nums1.len();
        let mut arr: Vec<(i32, i32)> = (0..n).map(|i| (nums2[i], nums1[i])).collect();
        arr.sort_by(|a, b| b.0.cmp(&a.0));
        use std::collections::BinaryHeap;
        let mut pq = BinaryHeap::new();
        let mut sum = 0i64;
        let mut ans = 0i64;
        for (b, a) in arr {
            pq.push(-a);
            sum += a as i64;
            if pq.len() > k as usize {
                sum += pq.pop().unwrap() as i64;
            }
            if pq.len() == k as usize {
                ans = ans.max(sum * b as i64);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maxScore(nums1: number[], nums2: number[], k: number): number {
        const arr = nums2.map((b, i) => [b, nums1[i]]).sort((a, b) => b[0] - a[0]);
        const pq: number[] = [];
        let sum = 0, ans = 0;
        for (const [b, a] of arr) {
            pq.push(a);
            pq.sort((x, y) => x - y);
            sum += a;
            if (pq.length > k) sum -= pq.shift()!;
            if (pq.length === k) ans = Math.max(ans, sum * b);
        }
        return ans;
    }
}