Maximum Subsequence Score Problem#
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
```clike
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.
|
1
2
3
4
5
6
7
8
9
10
11
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#
- Pair up elements from
nums1 and nums2 as (nums1[i], nums2[i]).
- Sort pairs by
nums2 in descending order.
- Use a min-heap to keep track of the largest
k values from nums1 as we iterate.
- For each pair, add
nums1 to the heap and sum, and if the heap size exceeds k, remove the smallest.
- When the heap size is exactly
k, calculate the score as sum * nums2 and update the maximum.
- Return the maximum score found.
Complexity#
- ⏰ Time complexity:
O(n log n) — Sorting and heap operations.
- 🧺 Space complexity:
O(k) — For the heap.
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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;
}
}
|