2542. Maximum Subsequence Score LeetCode Solution

In this guide, you will get 2542. Maximum Subsequence Score LeetCode Solution with the best time and space complexity. The solution to Maximum Subsequence Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Subsequence Score solution in C++
Maximum Subsequence Score solution in Java
Maximum Subsequence Score solution in Python
Additional Resources

2542. Maximum Subsequence Score LeetCode Solution image

Problem Statement of Maximum Subsequence Score

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.

Example 1:

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.

Example 2:

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.

Constraints:

n == nums1.length == nums2.length
1 <= n <= 105
0 <= nums1[i], nums2[j] <= 105
1 <= k <= n

Complexity Analysis

Time Complexity: O(\texttt{sort} + n\log k)
Space Complexity: O(n)

2542. Maximum Subsequence Score LeetCode Solution in C++

class Solution {
 public:
  // Same as 1383. Maximum Performance of a Team
  long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
    long ans = 0;
    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;
  }
};
/* code provided by PROGIEZ */

2542. Maximum Subsequence Score LeetCode Solution in Java

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, Comparator.comparing(Pair::getKey, Comparator.reverseOrder()));

    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;
  }
}
// code provided by PROGIEZ

2542. Maximum Subsequence Score LeetCode Solution in Python

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
 # code by PROGIEZ