You are given an integer n. An integer array nums of length $n + 1$ is created according to the following rules:

• nums[$0$] = $0$
• nums[$1$] = $1$
• nums[$2 \cdot i$] = nums[$i$] for $2 \le 2 \cdot i \le n$
• nums[$2 \cdot i + 1$] = nums[$i$] + nums[$i + 1$] for $2 \le 2 \cdot i + 1 \le n$

Return the maximum value in the generated array nums.

Constraints:

• $0 \le n \le 100$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.