1.题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2，两者长度都是 n，再给你一个正整数 k。你必须从 nums1 中选一个长度为 k 的子序列对应的下标。
对于选择的下标 i₀, i₁, …, i_k - 1，你的分数定义如下：

nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的最小值 。
用公示表示： (nums1[i₀] + nums1[i₁] +…+ nums1[i_k - 1]) * min(nums2[i₀] , nums2[i₁], … ,nums2[i_k - 1]) 。
请你返回最大可能的分数。

一个数组的子序列下标是集合 {0, 1, …, n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。

示例 1：
输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
输出：12
解释：
四个可能的子序列分数为：

• 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
• 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
• 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
• 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
  所以最大分数为 12 。

示例 2：
输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
输出：30
解释：
选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。

提示：
n == nums1.length == nums2.length
1 <= n <= 10⁵
0 <= nums1[i], nums2[j] <= 10⁵
1 <= k <= n

2.思路

（1）贪心算法
思路参考该 LeetCode 用户题解。

3.代码实现（Java）

//思路1————贪心算法
class Solution {public long maxScore(int[] nums1, int[] nums2, int k) {int n = nums1.length;long res = 0L;Integer[] sorts = new Integer[n];for (int i = 0; i < n; i++) {sorts[i] = i;}//将 nums2 进行降序排序，排序后的下标结果映射到 sorts 中Arrays.sort(sorts, (a, b) -> nums2[b] - nums2[a]);PriorityQueue<Integer> queue = new PriorityQueue<>();// sum 保存 nums1 中长度为 k 的子序列和long sum = 0L;for (int i = 0; i < k - 1; i++) {sum += nums1[sorts[i]];queue.offer(nums1[sorts[i]]);}for (int i = k - 1; i < n; i++) {sum += nums1[sorts[i]];queue.offer(nums1[sorts[i]]);//更新 resres = Math.max(res, nums2[sorts[i]] * sum);sum -= queue.poll();}return res;}
}