Leetcode 2542. Maximum Subsequence Score
Pick k indices to maximize (sum of chosen nums1 values) * (minimum of the chosen nums2 values); the core challenge is trading off a large nums1 sum against keeping the nums2 minimum high. A common pattern is to treat each nums2 as a candidate minimum (by sorting nums2 descending) and greedily maintain the largest nums1 contributions (e.g., with a min-heap) to evaluate the best product.
Asked at:
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late October, 2024
Mid-level
Divide a sequence of positive integers into non-empty contiguous subsequences. Find the maximum score, where score is the number of subsequences whose sum of elements is at least a given threshold. The sequence, number of parts, and threshold are given as input. Expected time complexity is O(nlogn).
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.