Practice/Google/Leetcode 2542. Maximum Subsequence Score

Leetcode 2542. Maximum Subsequence Score

CodingOptional

Problem

You are assembling a team from a pool of candidates. Each candidate has two attributes:

• An efficiency score (how much they contribute to the team's output)
• A speed rating (how fast they work)

You must select exactly k candidates to form your team. The team's performance score is calculated as:

Performance Score = (Sum of efficiency scores) × (Minimum speed among selected candidates)

Your goal is to select k candidates that maximize the performance score.

Requirements

1. Select exactly k candidates from the available pool
2. Calculate the sum of their efficiency scores
3. Find the minimum speed rating among the selected candidates
4. Return the maximum possible performance score (sum of efficiencies × minimum speed)

Constraints

• 1 ≤ k ≤ efficiency.length ≤ 105
• efficiency.length == speed.length
• 1 ≤ efficiency[i] ≤ 108
• 1 ≤ speed[i] ≤ 108
• The answer may be large, but will fit in a 64-bit integer

Examples

Example 1:

Input: efficiency = [3, 3, 3], speed = [2, 3, 3], k = 2 Output: 18 Explanation: Select the last two candidates (indices 1 and 2). Sum of efficiencies = 3 + 3 = 6 Minimum speed = min(3, 3) = 3 Performance score = 6 × 3 = 18

Example 2:

Input: efficiency = [5], speed = [10], k = 1 Output: 50 Explanation: Only one candidate is available. Sum of efficiencies = 5 Minimum speed = 10 Performance score = 5 × 10 = 50

Example 3:

Input: efficiency = [2, 8, 5], speed = [5, 7, 1], k = 3 Output: 15 Explanation: Must select all three candidates. Sum of efficiencies = 2 + 8 + 5 = 15 Minimum speed = min(5, 7, 1) = 1 Performance score = 15 × 1 = 15