Sponsored
Sponsored
This approach involves sorting the piles of coins first. After sorting, one can consistently select the second largest pile from each group of three piles (Alice's bigger pile, your pile, and Bob's smaller pile) to maximize your coins.
By sorting the piles in descending order, the strategy becomes easier. Alice will always pick the first pile, you will always pick the second pile, and Bob will take the third.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
1def maxCoins(piles):
2 piles.sort()
3 result = 0
4 n = len(piles) // 3
5 for i in range(n, len(piles), 2):
6 result += piles[i]
7 return result
8
9piles = [2, 4, 1, 2, 7, 8]
10print(maxCoins(piles))We sort the piles array, then iterate through the elements starting from the index n, taking every second element after to sum up to our result.
Another approach, although less direct than sorting, involves analyzing the positions of piles through controlled index manipulation to ensure Alice always takes the maximum pile, you take the second, and Bob takes the least of the three for every set of operations.
Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.
1using System.Linq;
public class Solution {
public int MaxCoins(int[] piles) {
Array.Sort(piles);
int result = 0;
int index = piles.Length - 2;
for (int i = 0; i < piles.Length / 3; i++) {
result += piles[index];
index -= 2;
}
return result;
}
public static void Main() {
int[] piles = new int[] {2, 4, 1, 2, 7, 8};
Solution sol = new Solution();
Console.WriteLine(sol.MaxCoins(piles));
}
}In C#, after sort, increment sums from a patterned indexed decrement process, thus awarding coins in specific slots you need.