Skip to content

2542. Maximum Subsequence Score 👍

  • Time: $O(\texttt{sort} + n\log k)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  // Same as 1383. Maximum Performance of a Team
  long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
    long long ans = 0;
    long long sum = 0;
    // (nums2[i], nums1[i]) sorted by nums2[i] in descending order.
    vector<pair<int, int>> A;
    priority_queue<int, vector<int>, greater<>> minHeap;

    for (int i = 0; i < nums1.size(); ++i)
      A.emplace_back(nums2[i], nums1[i]);

    ranges::sort(A, greater<>());

    for (const auto& [num2, num1] : A) {
      minHeap.push(num1);
      sum += num1;
      if (minHeap.size() > k)
        sum -= minHeap.top(), minHeap.pop();
      if (minHeap.size() == k)
        ans = max(ans, sum * num2);
    }

    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
25
26
27
28
class Solution {
  // Same as 1383. Maximum Performance of a Team
  public long maxScore(int[] nums1, int[] nums2, int k) {
    long ans = 0;
    long sum = 0;
    // (nums2[i], nums1[i]) sorted by nums2[i] in descending order.
    Pair<Integer, Integer>[] A = new Pair[nums1.length];
    Queue<Integer> minHeap = new PriorityQueue<>();

    for (int i = 0; i < nums1.length; ++i)
      A[i] = new Pair<>(nums2[i], nums1[i]);

    Arrays.sort(A, (a, b) -> Integer.compare(b.getKey(), a.getKey()));

    for (Pair<Integer, Integer> a : A) {
      final int num2 = a.getKey();
      final int num1 = a.getValue();
      minHeap.offer(num1);
      sum += num1;
      if (minHeap.size() > k)
        sum -= minHeap.poll();
      if (minHeap.size() == k)
        ans = Math.max(ans, sum * num2);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  # Same as 1383. Maximum Performance of a Team
  def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
    ans = 0
    summ = 0
    # (nums2[i], nums1[i]) sorted by nums2[i] in descending order.
    A = sorted([(num2, num1)
               for num1, num2 in zip(nums1, nums2)], reverse=True)
    minHeap = []

    for num2, num1 in A:
      heapq.heappush(minHeap, num1)
      summ += num1
      if len(minHeap) > k:
        summ -= heapq.heappop(minHeap)
      if len(minHeap) == k:
        ans = max(ans, summ * num2)

    return ans