Watch 10 video solutions for Maximum Subsequence Score, a medium level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 33,051 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.
For chosen indices i0, i1, ..., ik - 1, your score is defined as:
nums1 multiplied with the minimum of the selected elements from nums2.(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).Return the maximum possible score.
A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.
Example 1:
Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 Output: 12 Explanation: The four possible subsequence scores are: - We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7. - We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. - We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. - We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8. Therefore, we return the max score, which is 12.
Example 2:
Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1 Output: 30 Explanation: Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.
Constraints:
n == nums1.length == nums2.length1 <= n <= 1050 <= nums1[i], nums2[j] <= 1051 <= k <= nProblem Overview: You are given two arrays nums1 and nums2 and an integer k. Choose exactly k indices such that the score (sum of selected nums1) * (minimum selected nums2) is maximized. The challenge is balancing a large sum from nums1 while keeping the minimum value from nums2 as high as possible.
Approach 1: Sorting with Priority Queue (O(n log n) time, O(k) space)
The key observation: if a value from nums2 becomes the minimum of the chosen subsequence, then every other selected element must have nums2 greater than or equal to it. Sort pairs (nums1[i], nums2[i]) in descending order of nums2. As you iterate, treat the current nums2 as the minimum candidate. Maintain a min-heap of the largest k values from nums1 and track their running sum. Each time the heap reaches size k, compute the score using the current nums2. The heap ensures you always keep the best k contributors to the sum while iterating through decreasing minimum values. This approach combines sorting, greedy selection, and a priority queue to efficiently explore all valid minimum candidates.
Approach 2: Divide and Conquer (Optimal Subsequence Selection) (O(n log n) time, O(n) space)
Another way to think about the problem is recursively splitting the candidate range of indices after sorting by nums2. Each segment represents a potential range where a specific nums2 value acts as the minimum. Within each segment, select the best k contributors from nums1 and propagate partial results upward. The divide-and-conquer structure reduces repeated work by reusing partial sums and candidate sets across recursive segments. While the complexity remains O(n log n), this approach is useful when implementing language-specific optimizations or when integrating with segment-based selection techniques.
Recommended for interviews: The sorting + priority queue solution is the expected answer. It demonstrates strong algorithmic intuition: reduce the problem by fixing the minimum nums2, then greedily maximize the sum using a heap. Interviewers typically want to see the insight that sorting by nums2 converts the "minimum constraint" into a linear scan.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Priority Queue | O(n log n) | O(k) | General optimal solution; standard interview approach combining sorting and heap |
| Divide and Conquer Subsequence Selection | O(n log n) | O(n) | Useful for recursive or segment-based implementations where candidate ranges are processed independently |