# 2542. Maximum Subsequence Score
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/maximum-subsequence-score/description/
## Code

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        total = 0
        res = 0
        heap = []
        pairs = zip(nums1,nums2)
        sorted_pairs = sorted(pairs, key = lambda x:x[1], reverse = True)
        for pair in sorted_pairs:
            num1,num2 = pair
            heappush(heap,num1)
            total += num1
            if len(heap)>k:
                total -= heappop(heap)
            if len(heap) == k :
                res = max(res, total*num2)
        return res

## 題意
* 這道題目要求從兩個相等長度的陣列 nums1 和 nums2 中各選擇一個長度為 k 的子序列
* 對於所選的索引子序列，我們需要計算一個分數，該分數由以下公式給出：

1. 分數 = (nums1[i0] + nums1[i1] + ... + nums1[ik-1]) * min(nums2[i0], nums2[i1], ..., nums2[ik-1])

2. 其中i0, i1, ..., ik-1為所選的索引，min()表示選擇的nums2元素的最小值。

* 我們的目標是找到可能的最大分數。
## 思路
* 使用 nums2 的序列由大到小排序 pairs = zip(nums1,nums2)
* 遍歷每個 pairs ，計算目前的 total 並乘上目前的 nums 2，如果得出來的答案有比前一個大，就更新 res （用來儲存目前最大的結果）

## 解法

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        total = 0 # 用來算 nums1 的總和
        res = 0 # 用來更新分數
        heap = 
        pairs = zip(nums1,nums2) # 把 nums1 、 nums2 壓成對，這樣他們才會共用 index
        sorted_pairs = sorted(pairs, key = lambda x:x[1], reverse = True) # 依照 nums2 把 pair 由大到小排列
        for pair in sorted_pairs:
            num1,num2 = pair
            heappush(heap,num1) # 把 num1 一個一個擠進去 heap
            total += num1 # 算 nums1 的總和
            if len(heap)>k: # 如果 heap 超過指定長度，把最小的丟掉、剪掉
                total -= heappop(heap)
            if len(heap) == k :
                res = max(res, total*num2)# 用來更新分數
        return res

* 使用 nums2 去做排序的目的是為了在遍歷時能夠優先處理較大的 nums2 元素，從而使得得分最大化