[
array
math
greedy
sort
game
]
Leetcode 1561. Maximum Number of Coins You Can Get
Problem statement
https://leetcode.com/problems/maximum-number-of-coins-you-can-get/
Solution
Sort elements, then if we each time choose the smallest and two biggest piles, we will have sum(A[n//3::2])
.
Complexity
It is O(n log n)
for time and O(n)
for space.
Code
class Solution:
def maxCoins(self, A):
A = sorted(A)
n = len(A)
return sum(A[n//3::2])