The permutations game is a simple solitaire game played on a rectangular board. The board is divided into N squares, arranged in a row. Each square of the board has a distinct number between 1 and N, inclusive, printed on it. Each square also has a position. The leftmost square has position 1, the rightmost square has position N, and positions are numbered consecutively from left to right.
+---+---+---+---+---+---+
| 3 | 2 | 4 | 1 | 6 | 5 |
+---+---+---+---+---+---+
1 2 3 4 5 6
In this example for N=6 you can see the board with the numbers printed on it. Below each square is
its position.
This game is played in the following way: First, the player chooses any square as his starting square and steps on it. At each step, he will look at the number printed on the square on which he is standing, and then move to the square at that position. He repeats this until he returns to his starting square.
In the board shown above, the player might start at position 3. He would see the 4 printed on that square and move to position 4. Then, he would see a 1 and move to the position 1. Finally, he would see a 3 and return to his starting square, and the game would end there. If he started at position 2, he would see the 2 printed on that square, move to position 2 (where he was already standing), and stop there. Depending on where he started, he would visit a different number of squares (3 in the first example, and 1 in the second example). The goal of the game is to select the starting square that allows you to visit the greatest number of squares possible.
The board will be given as a int[], where the ith element is the value printed on the square at position i (i is a 1-based index). Return the maximum number of squares the player can visit if he selects his starting square optimally.
|