Maximum subsequence score

Array Greedy Sorting Heap (Priority Queue)

54.6% acceptance

Feb 25, 2026

3149

211

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: (nums1[i0] + nums1[i1] + ... + nums1[ik-1]) * min(nums2[i0], nums2[i1], ..., nums2[ik-1]) Return the maximum possible score.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let k = k as usize;
    let n = nums1.len();

    // Sort indices by nums2 in descending order
    let mut indices: Vec<usize> = (0..n).collect();
    indices.sort_unstable_by(|&a, &b| nums2[b].cmp(&nums2[a]));

    let mut heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    let mut sum = 0i64;
    let mut ans = 0i64;

    for &i in &indices {
      heap.push(Reverse(nums1[i]));
      sum += nums1[i] as i64;
      if heap.len() > k {
        let Reverse(min_val) = heap.pop().unwrap();
        sum -= min_val as i64;
      }
      if heap.len() == k {
        ans = ans.max(sum * nums2[i] as i64);
      }
    }
    ans
  }
}