Choose up to children to maximize the total happiness gained, where selecting a child reduces the happiness contribution of later selections.
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.
happiness: an array of integersk: the maximum number of children you may select1 <= happiness.lengthk >= 11max(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
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.