Problem Statement
Nam and Quang are playing a game with a sequence of integers A. In the game they take alternating turns. Nam plays first.
In Nam's turn he has to choose two consecutive elements of A. Once he does so, he has to erase the larger of these two elements. (If they are equal, he erases one of them, it does not matter which one.)
Quang's turn also begins with him choosing two consecutive elements of A. However, Quang always erases the smaller of those two elements.
The game terminates when only one element of A remains. Its value V is the result of the game. Nam's objective is to maximize V, while Quang's objective is to minimize V.
Assume that both players play optimally. Determine and return the value of V.
Definition
- Class:
- MinMaxGame
- Method:
- lastNumber
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int lastNumber(int[] A)
- (be sure your method is public)
Notes
- Whenever an element gets erased from A, its neighbors become adjacent to each other.
Constraints
- A will have between 2 and 100 elements, inclusive.
- Each element of A will be between 1 and 100, inclusive.
Examples
{3, 2, 1}Returns: 3
There are 2 possible scenarios: - Scenerio 1: In the first turn, Nam chooses the first two elements of A, then erases the larger one. The sequence A now becomes {2, 1}. In the second turn, Quang erases the smaller one amongst the two elements remaining in A. The sequence A now becomes {2}. The game terminates, V = 2. - Scenerio 2: In the first turn, Nam chooses the last two elements of A, then erases the larger one. The sequence A now becomes {3, 1}. In the second turn, Quang erases the smaller one amongst the two elements remaining in A. The sequence A now becomes {3}. The game terminates, V = 3. Because Nam's objective is to maximize V, he will choose scenerio 2.{2, 5, 3, 7}Returns: 2
{4, 5, 1, 6, 5}Returns: 5