> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Maximum Subsequence Score Python Solution

> Tested Python solution for LeetCode 2542 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 2542, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Greedy](/catalog/topics/greedy), [Sorting](/catalog/topics/sorting), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/maximum-subsequence-score/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2542   # by problem number
lcpy gen -s maximum_subsequence_score   # by problem name
```

## Problem

You are given two \<strong>0-indexed\</strong> integer arrays \<code>nums1\</code> and \<code>nums2\</code> of equal length \<code>n\</code> and a positive integer \<code>k\</code>. You must choose a \<strong>subsequence\</strong> of indices from \<code>nums1\</code> of length \<code>k\</code>.

\<p>For chosen indices \<code>i\<sub>0\</sub>\</code>, \<code>i\<sub>1\</sub>\</code>, ..., \<code>i\<sub>k - 1\</sub>\</code>, your \<strong>score\</strong> is defined as:\</p>

\<ul>
\<li>The sum of the selected elements from \<code>nums1\</code> multiplied with the \<strong>minimum\</strong> of the selected elements from \<code>nums2\</code>.\</li>
\<li>It can defined simply as: \<code>(nums1\[i\<sub>0\</sub>] + nums1\[i\<sub>1\</sub>] +...+ nums1\[i\<sub>k - 1\</sub>]) \* min(nums2\[i\<sub>0\</sub>] , nums2\[i\<sub>1\</sub>], ... ,nums2\[i\<sub>k - 1\</sub>])\</code>.\</li>
\</ul>

\<p>Return \<em>the \<strong>maximum\</strong> possible score.\</em>\</p>

\<p>A \<strong>subsequence\</strong> of indices of an array is a set that can be derived from the set \<code>\{0, 1, ..., n-1}\</code> by deleting some or no elements.\</p>

### Examples

```
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.
```

```
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 \<= 10^5
* 0 \<= nums1\[i], nums2\[j] \<= 10^5
* 1 \<= k \<= n

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_subsequence_score/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_subsequence_score/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def max_score(self, nums1: list[int], nums2: list[int], k: int) -> int:
        pairs = sorted(zip(nums1, nums2, strict=True), key=lambda p: p[1], reverse=True)
        heap: list[int] = []
        total = 0
        best = 0
        for n1, n2 in pairs:
            heapq.heappush(heap, n1)
            total += n1
            if len(heap) > k:
                total -= heapq.heappop(heap)
            if len(heap) == k:
                best = max(best, total * n2)
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.