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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int maxCoins(std::vector<int>& piles) {
6 std::sort(piles.begin(), piles.end(), std::greater<int>());
7 int result = 0;
8 for (int i = 1, j = piles.size() - 1; i < j; i += 2, --j) {
9 result += piles[i];
10 }
11 return result;
12}
13
14int main() {
15 std::vector<int> piles = {2, 4, 1, 2, 7, 8};
16 std::cout << maxCoins(piles) << std::endl;
17 return 0;
18}The vector is sorted in descending order and a loop is used to accumulate your coins by picking the second pile each time. Sorting ensures that Alice gets the max, you get the second max, and Bob gets the minimum of the three choices.
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.
1
In JavaScript, first sort and use a combination approach of count down monitoring per justified index pick notion.