Maximum Subsequence Score

medium heap sorting greedy

Problem

Given two equal-length arrays v (values) and w (multipliers), pick exactly k indices to maximise (sum of chosen v's) × (min of chosen w's). Sort indices by w descending; sweep while keeping a min-heap of the top k v's seen — at each step the multiplier is fixed (the current w), so the answer is heapSum × w.

Inputv = [1,3,3,2], w = [2,1,3,4], k = 3

Output12

Pick indices 0, 2, 3 → values sum 6, min mult 2 → 12.

v (comma-separated)

w (comma-separated, same length)

import heapq
def max_score(v, w, k):
    idx = sorted(range(len(v)), key=lambda i: -w[i])
    heap = []; s = 0; best = 0
    for i in idx:
        heapq.heappush(heap, v[i]); s += v[i]
        if len(heap) > k: s -= heapq.heappop(heap)
        if len(heap) == k: best = max(best, s * w[i])
    return best

function maxScore(v, w, k) {
  const idx = v.map((_, i) => i).sort((a, b) => w[b] - w[a]);
  const heap = []; let sum = 0, best = 0;
  for (const i of idx) {
    heap.push(v[i]); heap.sort((a, b) => a - b); sum += v[i];
    if (heap.length > k) sum -= heap.shift();
    if (heap.length === k) best = Math.max(best, sum * w[i]);
  }
  return best;
}

class Solution {
    public long maxScore(int[] v, int[] w, int k) {
        Integer[] idx = new Integer[v.length];
        for (int i = 0; i < v.length; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> w[b] - w[a]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        long sum = 0, best = 0;
        for (int i : idx) {
            heap.offer(v[i]); sum += v[i];
            if (heap.size() > k) sum -= heap.poll();
            if (heap.size() == k) best = Math.max(best, sum * w[i]);
        }
        return best;
    }
}

long long maxScore(vector<int>& v, vector<int>& w, int k) {
    vector<int> idx(v.size());
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) { return w[a] > w[b]; });
    priority_queue<int, vector<int>, greater<int>> heap;
    long long sum = 0, best = 0;
    for (int i : idx) {
        heap.push(v[i]); sum += v[i];
        if ((int)heap.size() > k) { sum -= heap.top(); heap.pop(); }
        if ((int)heap.size() == k) best = max(best, sum * (long long)w[i]);
    }
    return best;
}

Explanation

The score is (sum of chosen v's) × (min of chosen w's) over exactly k picks. Just like the team-performance problem, the slippery part is the minimum multiplier, so we pin it down by sorting indices by w descending.

Sweeping that order, the current index's w is the smallest multiplier among everything seen so far. So if we treat it as the group's minimum, all teammates come from earlier indices, and the multiplier for the whole group is fixed at this w.

To get the largest value sum, we keep a min-heap of the chosen v's. We push each v and keep a running sum; when the heap exceeds k, we pop the smallest v so only the top k values remain.

Once the heap holds exactly k values, a valid score is sum × w for the current w, and we keep the best one across the whole sweep.

Example: v=[1,3,3,2], w=[2,1,3,4], k=3. Sorting by w descending and sweeping, the best group is values summing to 6 with minimum multiplier 2, giving 6 × 2 = 12.

Time: O(n log n) Space: O(k)