解題程式碼

var maxScore = function (nums1, nums2, k) {
  let max = 0;
  let sum = 0;
  const minHeap = new MinPriorityQueue();
  const pairs = nums1.map((num, i) => [num, nums2[i]]).sort((a, b) => b[1] - a[1]);

  for (const [front, end] of pairs) {
    sum += front;
    minHeap.enqueue(front);

    if (minHeap.size() === k) {
      max = Math.max(max, sum * end);
      sum -= minHeap.dequeue().element; // 當儲存 k 個元素在 Min Heap 時，在 max 計算完後就移除一個，可以保持 k 次運算後，Min Heap 永遠有 k 個元素
    }
  }
  return max;
};

解題思路、演算法

這題乍看好像用動態規劃解題，但實際上不是。

題目要的結果是 (nums1 子序列的總和) * (nums2 子序列的最小值) 要最大，那麼目標就是 nums1 子序列的總和和 nums2 子序列的最小值都越大越好。

先用 nums1 & nums2 陣列組出一個新的二維陣列，相同索引的元素組成 pair 放入該二維陣列，例如 nums1 = [1,3,3,2], nums2 = [2,1,3,4]，則產生 [[2, 4], [3, 3], [1, 2], [3, 1]]，然後根據後者元素的大小做排序。

然後建立一個 Min Heap，size 為 k，用其特性剔除在 nums1 中子序列較小的值，保障每回合選到的子序列總和最大。

解法的時間、空間複雜度

時間複雜度: O(n * log n)，sorting，O(n * log k) 是 heap 操作的時間複雜度，小於前者
空間複雜度: O(n + k)，儲存 pairs 二維陣列 & 在 Min Heap 的 k 個元素

參考資料

Maximum Subsequence Score - Leetcode 2542 - Python