Maximum Score from Non-Adjacent Tiles
A game contains tiles with non-negative scores. A player may select tiles to collect their scores, but two neighboring tiles cannot both be selected.
Determine the maximum score the player can collect when the tiles are arranged in a straight line and when they are arranged in a circle.
Rules
- Each tile may be selected at most once.
- Two neighboring tiles cannot both be selected.
- The player may leave any number of tiles unselected.
- If the circular layout contains only one tile, that tile may be selected.
Maximum Score from Non-Adjacent Tiles
Straight-Line Tiles
int maximumLineScore(List<Integer> tileScores)
tileScores contains the score of each tile in a straight line.- The method returns the maximum total score obtainable without selecting neighboring tiles.
Circular Tiles
int maximumCircleScore(List<Integer> tileScores)
tileScores contains the score of each tile in a circle.- The first and last tiles are also considered neighbors.
- The method returns the maximum total score obtainable without selecting neighboring tiles.
Constraints
1 ≤ tileScores.size() ≤ 1000 ≤ tileScores.get(i) ≤ 1,000 for every 0 ≤ i < tileScores.size().
Examples
Example 1
maximumLineScore( tileScores = List.of(5, 11, 4, 9, 2) )
Output: 20
Select the tiles worth 11 and 9. They are not neighbors, and their total score is 20.
Example 2
maximumLineScore( tileScores = List.of(12, 3, 6, 10) )
Output: 22
Select the first and last tiles to collect 12 + 10 = 22 points.
Example 3
maximumCircleScore( tileScores = List.of(9, 2, 7, 4) )
Output: 16
Select the tiles worth 9 and 7. Their total score is 16.
Example 4
maximumCircleScore( tileScores = List.of(5, 12, 6, 11, 4) )
Output: 23
Select the tiles worth 12 and 11. They are not neighbors, and their total score is 23.