---
# System prepended metadata

title: 2542. Maximum Subsequence Score
tags: [Leetcode, Priority Queue, Medium, Greedy]

---

# 2542. Maximum Subsequence Score
###### tags: `Leetcode` `Medium` `Priority Queue` `Greedy`
Link: https://leetcode.com/problems/maximum-subsequence-score/description/
## 思路
和[1383. Maximum Performance of a Team](https://hackmd.io/bKCHp-8yTLi42s5emUM0WQ)一样
找到用每个nums2里面的值当最小值的时候 score的最大值 (nums1对应元素的和用priority queue实现)
然后取他们中最大的一个即可
## Code
```python=
class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        currSum = ans = 0
        pq = []
        for a, b in sorted(list(zip(nums1, nums2)), key = lambda ab: -ab[1]):
            heappush(pq, a)
            currSum += a
            if len(pq)>k: currSum -= heappop(pq)
            if len(pq)==k: ans = max(ans, currSum*b)
        return ans
```
```java=
class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int[][] arr = new int[n][2];
        for(int i=0; i<n; i++){
            arr[i][0] = nums1[i];
            arr[i][1] = nums2[i];
        }
        Arrays.sort(arr, (a,b)->(b[1]-a[1]));
        Queue<Integer> pq = new PriorityQueue<>();
        long currSum = 0, ans = 0;
        for(int i=0; i<n; i++){
            currSum += arr[i][0];
            pq.add(arr[i][0]);
            if(pq.size()>k) currSum -= pq.poll();
            if(pq.size()==k) ans = Math.max(ans, currSum*arr[i][1]);
        }
        return ans;
    }
}
```