解題說明
Maximum Subsequence Score
題目描述：給定兩個長度相同的整數陣列 nums1 和 nums2，以及整數 k。選取 k 個索引組成子序列，分數定義為：nums1 中被選取的 k 個值的總和，乘以 nums2 中被選取的 k 個值中的最小值。求最大分數。
解題思路：關鍵觀察：若固定「被選取的 nums2 最小值」為 nums2[i]，那麼 nums2 中其他被選的值都必須 >= nums2[i]，而 nums1 應盡量選對應的大值。策略：按 nums2 降序排列所有配對。從左掃描（nums2 值遞減），用最小堆維護當前選入的 k 個 nums1 值（保持堆的 top 為最小）。當已有 k 個元素時，若新的 nums1[i] 大於堆頂，則替換。每次堆大小恰好達到 k 時，計算 heapSum * nums2[i] 並更新答案。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 排序 O(n log n)；每次 heap 操作 O(log k)，共 n 次，合計 O(n log k) ⊆ O(n log n)。
空間複雜度：O(n) — 儲存配對陣列 O(n)，堆最多 k+1 個元素 O(k)。
虛擬碼
1. Create pairs of (nums2[i], nums1[i]), sort descending by nums2 2. Initialize min-heap, heapSum = 0, ans = 0 3. For each (v2, v1) in sorted pairs: a. Push v1 to heap, heapSum += v1 b. If heap size > k: heapSum -= heap.top(); pop heap c. If heap size == k: ans = max(ans, heapSum * v2) 4. Return ans
其他解法
暴力枚舉（O(C(n,k) * k)）：枚舉所有 C(n,k) 種索引組合，計算每個分數。當 n=10, k=3 尚可接受，但 n 可到 1e5，完全不可行。
DP 方法：按 nums2 排序後，維護每個可能的「已選 m 個」的最大 nums1 總和，但狀態轉移需要每次保持最優的 k 個值，實作複雜度與 heap 解法相近。
固定 nums2 最大值而非最小值：若按 nums2 升序掃描，固定每次掃描位置的 nums2[i] 為最小值，同樣可行，但需要「已遇到的元素中選 k 個最大 nums1」，同樣用 max-heap 維護前 k 大，邏輯對稱。
延伸思考
- 若分數定義改為
sum(nums1) * max(nums2)（乘以最大值），解法應如何調整？ - 如果 k 是動態查詢的（多個不同 k 值），能否預處理以加速回答？
- 此題與「帶限制的貪婪選擇」問題有何共通的解題框架？