Choose up to children to maximize the total happiness gained, where selecting a child reduces the happiness contribution of later selections.
Problem
You are given an array happiness, where happiness[i] is the initial happiness value of the -th child, and an integer k.
You may select at most k children, one per round. In each round, choose a child who has not been selected before. If the child currently has happiness x, you gain max(x, 0) happiness from that child, and then every unselected child's happiness effectively decreases by 1 for the next round.
Return the maximum total happiness you can collect.
Notes
- Once a child is selected, it cannot be selected again.
- If a child's effective happiness becomes non-positive, selecting it contributes nothing useful.
- The goal is to maximize the sum over all selected rounds.
Input Format
happiness: an array of integersk: the maximum number of children you may select
Output Format
- Return a single integer: the maximum possible total happiness.
Constraints
1 <= happiness.lengthk >= 1- Each round decreases the remaining unselected children's effective happiness by
1 - A selected child's contribution is
max(current_happiness, 0)
Example 1
Input
happiness = [1, 2, 3], k = 2
Output
5
Explanation
Pick the child with happiness 3 first, then the child with happiness 2. The total is 3 + 2 = 5.
Example 2
Input
happiness = [1, 1, 1], k = 3
Output
1
Explanation
The best choice is to pick any child first for 1 point. After that, the remaining effective happiness values are not positive, so taking more children adds no benefit.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.