Get Maximum in Generated Array

Problem: You are given an integer n. An array of length n + 1 is generated in the following way:

• arr[0] = 0
• arr[1] = 1
• arr[2 * i] = arr[i] when 2 <= 2 * i <= n
• arr[2 * i + 1] = arr[i] + arr[i + 1] when 2 <= 2 * i + 1 <= n

Return the maximum integer in the array arr​​​.

Example:

Input: n = 4
Output: 2
Explanation: Let's build the array:
  arr[0] = 0
  arr[1] = 1
  arr[(1 * 2) = 2] = arr[1] = 1
  arr[(1 * 2) + 1 = 3] = arr[1] + arr[2] = 1 + 1 = 2
  arr[(2 * 2) = 4] = arr[2] = 1
Hence, arr = [0,1,1,2,1], and the maximum is 2.

Approach: Let's just build the array from i = 0 to n according to the rules and get the maximum of the array.

Implementation in C#:

        public static int GetMaximumGenerated(int n)

        {

            if (n <= 1)

            {

                return n;

            }

            int[] nums = new int[n + 1];

            nums[0] = 0;

            nums[1] = 1;

            int max = int.MinValue;

            for (int i = 2; i <= n; ++i)

            {

                if (i % 2 == 0)

                {

                    nums[i] = nums[i / 2];

                }

                else

                {

                    nums[i] = nums[i / 2] + nums[i / 2 + 1];

                }

                max = Math.Max(max, nums[i]);

            }

            return max;

        }

Complexity: O(n)