# Maximum Subsequence Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-subsequence-score)
Canonical: https://scaleengineer.com/dsa/problems/maximum-subsequence-score
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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`

# Approaches
## Iterating Through All Potential Minimums
This approach iterates through every element in `nums2` and considers it as the potential minimum for a valid subsequence. For each potential minimum `nums2[i]`, it finds all other elements `j` where `nums2[j]` is greater than or equal to `nums2[i]`. From this group of candidates, it selects the `k` elements with the largest corresponding `nums1` values to maximize the sum. The score is then calculated and compared with the maximum score found so far.
**Time:** O(N^2 * logN). The outer loop runs `N` times. Inside, we iterate `N` times to build the `candidates` list (size up to `N`). Sorting this list takes `O(N log N)`. So, the total time is `N * (N + N log N) = O(N^2 log N)`. · **Space:** O(N). In each iteration of the outer loop, we create a `candidates` list that can store up to `N` elements.
**Pros:** Conceptually simpler than the optimized approach.; Correctly breaks down the problem by fixing one variable (the minimum value).
**Cons:** Very inefficient due to repeated work. For each potential minimum, it rescans the entire array and re-sorts a potentially large list.; Will result in a "Time Limit Exceeded" (TLE) error for large inputs as specified in the constraints.
### Explanation
The core idea is to fix the minimum element of the `nums2` subsequence and then find the best `nums1` sum. By iterating through every possible choice for this minimum value, we can explore all valid scenarios. For each choice, we gather all eligible elements and pick the best `k` of them to maximize the sum part of the score formula.

Here's the step-by-step algorithm:
1.  Initialize a variable `maxScore` to 0.
2.  Iterate through each index `i` from `0` to `n-1`.
3.  For each `i`, let `minVal = nums2[i]`. This `minVal` is our candidate for the minimum of the `k` chosen `nums2` values.
4.  Create a list of `nums1` values for all indices `j` where `nums2[j] >= minVal`. These are the `nums1` values we are allowed to choose from.
5.  If the size of this list is less than `k`, we cannot form a subsequence of length `k`, so we continue to the next `i`.
6.  If the list has `k` or more elements, sort it in descending order.
7.  Calculate the sum of the first `k` elements from the sorted list. This gives the maximum possible sum of `nums1` values for the chosen `minVal`.
8.  Calculate the current score by multiplying this sum with `minVal`.
9.  Update `maxScore = max(maxScore, currentScore)`.
10. After iterating through all possible `i`, `maxScore` will hold the result.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        long maxScore = 0;

        for (int i = 0; i < n; i++) {
            int currentMin = nums2[i];
            List<Integer> candidates = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (nums2[j] >= currentMin) {
                    candidates.add(nums1[j]);
                }
            }

            if (candidates.size() < k) {
                continue;
            }

            Collections.sort(candidates, Collections.reverseOrder());

            long currentSum = 0;
            for (int l = 0; l < k; l++) {
                currentSum += candidates.get(l);
            }

            maxScore = Math.max(maxScore, currentSum * currentMin);
        }

        return maxScore;
    }
}
```
### Algorithm
- Initialize `maxScore = 0`.
- For each index `i` from `0` to `n-1`:
    - Let `minVal = nums2[i]`.
    - Create a list `candidates` of all `nums1[j]` where `nums2[j] >= minVal`.
    - If `candidates.size() < k`, continue to the next `i`.
    - Sort `candidates` in descending order.
    - Calculate `currentSum` as the sum of the first `k` elements of `candidates`.
    - Update `maxScore = max(maxScore, currentSum * minVal)`.
- Return `maxScore`.

## Sorting with a Min-Heap (Priority Queue)
This is an optimized approach that avoids the repeated work of the previous method. The key idea is to process the elements in a specific order. We pair up `nums1[i]` and `nums2[i]` and sort these pairs based on `nums2` values in descending order. By iterating through the sorted pairs, we can efficiently maintain the sum of the `k` largest `nums1` values seen so far using a min-heap of size `k`.
**Time:** O(N log N). Sorting the pairs takes `O(N log N)`. The loop runs `N` times, and each heap operation (add/poll) takes `O(log K)`. So the loop takes `O(N log K)`. The total complexity is dominated by sorting, resulting in `O(N log N)`. · **Space:** O(N). We need `O(N)` space to store the pairs for sorting. The min-heap requires `O(K)` space. Thus, the total space complexity is `O(N + K) = O(N)`.
**Pros:** Highly efficient and passes the time limits for the given constraints.; Clever use of sorting and a min-heap to avoid re-computation. By processing elements in order of decreasing `nums2` values, we can maintain the sum of the top `k` `nums1` values incrementally.
**Cons:** The logic is more complex to understand compared to the brute-force approach.; Requires extra space for storing pairs, which could be a concern for extremely large N if memory is severely constrained.
### Explanation
The score is `(sum of k nums1 elements) * (min of k nums2 elements)`. If we fix the `min of k nums2 elements` to be `m`, we should choose `k` elements whose `nums2` values are all at least `m`, and whose `nums1` sum is maximized. This means we should pick the `k` largest `nums1` values from the pool of eligible elements.

To do this efficiently, we can iterate through all possible values of `m`. The possible values for `m` are the elements of `nums2`. Let's process these `m` values from largest to smallest.

The algorithm is as follows:
1.  Create an array of pairs, where each pair contains `(nums1[i], nums2[i])`.
2.  Sort this array of pairs in descending order based on the `nums2` values. This ensures that when we iterate through the pairs, the `nums2` value of the current pair is a candidate for the minimum, and all previously seen elements have a `nums2` value greater than or equal to it.
3.  Initialize a min-heap (PriorityQueue in Java) to keep track of the `k` largest `nums1` values encountered so far. Also, initialize `currentSum` to track the sum of elements in the heap and `maxScore` to 0.
4.  Iterate through the sorted pairs `(n1, n2)`:
    a. Add the current `nums1` value, `n1`, to the min-heap and to `currentSum`.
    b. If the heap's size exceeds `k`, it means we have `k+1` elements. To maintain the `k` largest, we must remove the smallest element. We poll from the min-heap (which removes the smallest element) and subtract it from `currentSum`.
    c. Once the heap's size reaches `k`, we have a valid group of `k` elements. The sum of their `nums1` values is `currentSum`. The minimum of their `nums2` values is the current `n2` (due to our sorting).
    d. Calculate the score `currentSum * n2` and update `maxScore` if it's larger.
5.  After the loop, `maxScore` holds the maximum possible score.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums1[i];
            pairs[i][1] = nums2[i];
        }

        // Sort pairs by nums2 in descending order
        Arrays.sort(pairs, (a, b) -> b[1] - a[1]);

        // Min-heap to store the k largest nums1 values
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        long currentSum = 0;
        long maxScore = 0;

        for (int i = 0; i < n; i++) {
            int n1 = pairs[i][0];
            int n2 = pairs[i][1];

            minHeap.add(n1);
            currentSum += n1;

            if (minHeap.size() > k) {
                currentSum -= minHeap.poll();
            }

            if (minHeap.size() == k) {
                maxScore = Math.max(maxScore, currentSum * n2);
            }
        }

        return maxScore;
    }
}
```
### Algorithm
- Create pairs `(nums1[i], nums2[i])`.
- Sort the pairs in descending order based on `nums2` values.
- Initialize a min-heap `pq`, `currentSum = 0`, `maxScore = 0`.
- For each pair `(n1, n2)` in the sorted list:
    - Add `n1` to `pq` and `currentSum`.
    - If `pq.size() > k`, remove the smallest element: `currentSum -= pq.poll()`.
    - If `pq.size() == k`, calculate score: `maxScore = max(maxScore, currentSum * n2)`.
- Return `maxScore`.

# Solutions
### Java

```java
class Solution {
public
  long maxScore(int[] nums1, int[] nums2, int k) {
    int n = nums1.length;
    int[][] nums = new int[n][2];
    for (int i = 0; i < n; ++i) {
      nums[i] = new int[]{nums1[i], nums2[i]};
    }
    Arrays.sort(nums, (a, b)->b[1] - a[1]);
    long ans = 0, s = 0;
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for (int i = 0; i < n; ++i) {
      s += nums[i][0];
      q.offer(nums[i][0]);
      if (q.size() == k) {
        ans = Math.max(ans, s * nums[i][1]);
        s -= q.poll();
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxScore(vector<int> &nums1, vector<int> &nums2, int k) {
    int n = nums1.size();
    vector<pair<int, int>> nums(n);
    for (int i = 0; i < n; ++i) {
      nums[i] = {-nums2[i], nums1[i]};
    }
    sort(nums.begin(), nums.end());
    priority_queue<int, vector<int>, greater<int>> q;
    long long ans = 0, s = 0;
    for (auto &[a, b] : nums) {
      s += b;
      q.push(b);
      if (q.size() == k) {
        ans = max(ans, s * -a);
        s -= q.top();
        q.pop();
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int: nums = sorted(zip(nums2, nums1), reverse=True) q = [] ans = s = 0 for a, b in nums: s += b heappush(q, b) if len(q) == k: ans = max(ans, s * a) s -= heappop(q) return ans

```