Split piles of coins into groups of 3: Alice gets max, you get second, Bob gets min. Maximize your coins.
Sort piles. In each triplet (from sorted), you always take second largest. Bob takes the smallest pile.
- Sort piles
- Bob takes first n/3 piles (smallest)
- You take every other pile from position n/3: indices n/3, n/3+2, n/3+4...
- Sum your piles
- Time Complexity: O(n log n)
- Space Complexity: O(1)