Maximum Number of Coins You Can Get
There are 3n piles of coins of varying size. You and your friends will take piles of coins as follows:
- In each step, you will choose any
3piles of coins, not necessarily consecutive. - Of your choice, Alice will pick the pile with the maximum number of coins.
- You will pick the next pile with the maximum number of coins.
- Your friend Bob will pick the last pile.
- Repeat until there are no more piles of coins.
Given an array of integers piles where piles[i] is the number of coins in the i^th pile, return the maximum number of coins that you can have.
Example 1
Input
piles = [2,4,1,2,7,8]Output
9Choosing triplets
(2, 7, 8) and (1, 2, 4) gives you 7 + 2 = 9 coins, which is optimal.Example 2
Input
piles = [2,4,5]Output
4With piles
[2, 4, 5], Alice takes 5, you take 4, and Bob takes 2.Constraints
- 3 <= piles.length <= 10^5
- piles.length % 3 == 0
- 1 <= piles[i] <= 10^4