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;
}

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