In this approach, the idea is to pair up elements of nums1 and nums2 into tuples. Then, sort these pairs by nums2 in descending order. This way, we process elements with higher values in nums2 first. Using a priority queue (min-heap), we can efficiently keep track of the k largest nums1 values, which we use to calculate the score. The maximum score is computed by iterating through potential minimums, maintaining the current sum of the largest k values seen so far.
Time Complexity: O(n log n) due to sorting and heap operations.
Space Complexity: O(k) for the min-heap storing k elements.
1#include <vector>
2#include <queue>
3#include <algorithm>
4
5int maxScore(std::vector<int>& nums1, std::vector<int>& nums2, int k) {
6 std::vector<std::pair<int, int>> pairs;
7 for (size_t i = 0; i < nums1.size(); ++i) {
8 pairs.emplace_back(nums2[i], nums1[i]);
9 }
10 std::sort(pairs.rbegin(), pairs.rend());
11 std::priority_queue<int, std::vector<int>, std::greater<>> min_heap;
12 long long current_sum = 0, max_score = 0;
13 for (const auto& [num2, num1] : pairs) {
14 min_heap.push(num1);
15 current_sum += num1;
16 if (min_heap.size() > k) {
17 current_sum -= min_heap.top();
18 min_heap.pop();
19 }
20 if (min_heap.size() == k) {
21 max_score = std::max(max_score, current_sum * num2);
22 }
23 }
24 return max_score;
25}
26
27// Example usage
28// std::cout << maxScore({1,3,3,2}, {2,1,3,4}, 3) << std::endl; // Output: 12This C++ solution follows a similar strategy, using std::vector to pair elements and std::sort for sorting. It uses a priority queue to efficiently manage the k largest nums1 elements and dynamically computes the score.
This approach emphasizes efficient subsequence selection by partitioning the array. Divide the array in such a way that potential results can be directly computed without redundant calculations. Use recursion to evaluate possible subsequences efficiently.
Time Complexity: O(n log n) primary by sorting and heap operations.
Space Complexity: O(k) for the priority queue.
1import java.util.*;
2
3public class Solution {
4 public int maxScore(int[] nums1, int[] nums2, int k) {
5 List<int[]> pairs = new ArrayList<>();
6 for (int i = 0; i < nums1.length; ++i) {
7 pairs.add(new int[]{nums2[i], nums1[i]});
8 }
9 pairs.sort((a, b) -> Integer.compare(b[0], a[0]));
10
11 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
12 long currentSum = 0, maxScore = 0;
13 for (int[] pair : pairs) {
14 int num2 = pair[0], num1 = pair[1];
15 minHeap.add(num1);
16 currentSum += num1;
17 if (minHeap.size() > k) {
18 currentSum -= minHeap.poll();
19 }
20 if (minHeap.size() == k) {
21 maxScore = Math.max(maxScore, currentSum * num2);
22 }
23 }
24 return (int) maxScore;
25 }
26
27 // Example usage
28 // public static void main(String[] args) {
29 // System.out.println(new Solution().maxScore(new int[]{1,3,3,2}, new int[]{2,1,3,4}, 3)); // Output: 12
30 // }
31}The Java implementation uses List to manage pairs and utilizes the built-in sorting method for ordering. It implements similar logic using priority queues to track k largest elements for scoring.