24/02/2018

[Java] Maximise alternate picks on array

Here's a simple game: gold pots with different amounts of coins are placed in a single line. Two players alternate in choosing one pot to pick from either side.
Find the maximum amount of gold a player can get.

And the solution is intuitive enough with only a big gotcha: while the game progresses, the same player does NOT always pick, therefore he will have turns where his total does NOT increase AND he is left with the WORST choice for the next turn.

This translates into a recursive algorithm where Math.max and Math.min are our friends. We must carefully track which player would get to pick during recursion and adapt the branching on PICK + MAX or only MIN depending on whose turn is it. The base case is when a single pot is left - and even here we must check for whose turn it is!

For complexity, since we are deciding between two options at each step, we get a scary O(2^N) time and space due to the stack recursion.

You can find my implementation of getMaxGoldFromPotsNoDP on my Gist alongside some test cases in GoldPotsJTests.

A slightly more complex solution that has overall better performance O(N^2) can be found in getMaxGoldFromPots instead.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.