Problem

You are given an integer n. A 0-indexed integer array nums of length n + 1 is generated in the following way:

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

Return****_themaximum integer in the array _nums​​​.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input: n = 7
Output: 3
Explanation: According to the given rules:
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is max(0,1,1,2,1,3,2,3) = 3.

Example 2

1
2
3

Input: n = 2
Output: 1
Explanation: According to the given rules, nums = [0,1,1]. The maximum is max(0,1,1) = 1.

Example 3

1
2
3

Input: n = 3
Output: 2
Explanation: According to the given rules, nums = [0,1,1,2]. The maximum is max(0,1,1,2) = 2.

Constraints

  • 0 <= n <= 100

Solution

Method 1 – Simulation and Array Construction

Intuition

The problem is a direct simulation: we build the array step by step using the given rules. For each index, we either copy a previous value or sum two previous values. The answer is simply the maximum value in the constructed array.

Approach

  1. If n is 0, return 0 (since the only value is 0).
  2. Initialize an array nums of size n+1 with nums[0]=0 and nums[1]=1 (if n>=1).
  3. For each index i from 2 to n:
    • If i is even, set nums[i] = nums[i//2].
    • If i is odd, set nums[i] = nums[i//2] + nums[i//2 + 1].
  4. Track the maximum value while building the array.
  5. Return the maximum value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        std::vector<int> nums(n + 1, 0);
        nums[1] = 1;
        int ans = 1;
        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];
            if (nums[i] > ans) ans = nums[i];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func getMaximumGenerated(n int) int {
    if n == 0 {
        return 0
    }
    nums := make([]int, n+1)
    nums[1] = 1
    ans := 1
    for i := 2; i <= n; i++ {
        if i%2 == 0 {
            nums[i] = nums[i/2]
        } else {
            nums[i] = nums[i/2] + nums[i/2+1]
        }
        if nums[i] > ans {
            ans = nums[i]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        int[] nums = new int[n + 1];
        nums[1] = 1;
        int ans = 1;
        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];
            if (nums[i] > ans) ans = nums[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun getMaximumGenerated(n: Int): Int {
        if (n == 0) return 0
        val nums = IntArray(n + 1)
        nums[1] = 1
        var ans = 1
        for (i in 2..n) {
            nums[i] = if (i % 2 == 0) nums[i / 2] else nums[i / 2] + nums[i / 2 + 1]
            if (nums[i] > ans) ans = nums[i]
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        nums: list[int] = [0] * (n + 1)
        nums[1] = 1
        ans = 1
        for i in range(2, n + 1):
            if i % 2 == 0:
                nums[i] = nums[i // 2]
            else:
                nums[i] = nums[i // 2] + nums[i // 2 + 1]
            if nums[i] > ans:
                ans = nums[i]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn get_maximum_generated(n: i32) -> i32 {
        if n == 0 { return 0; }
        let n = n as usize;
        let mut nums = vec![0; n + 1];
        nums[1] = 1;
        let mut ans = 1;
        for i in 2..=n {
            nums[i] = if i % 2 == 0 {
                nums[i / 2]
            } else {
                nums[i / 2] + nums[i / 2 + 1]
            };
            if nums[i] > ans {
                ans = nums[i];
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    getMaximumGenerated(n: number): number {
        if (n === 0) return 0;
        const nums: number[] = new Array(n + 1).fill(0);
        nums[1] = 1;
        let ans = 1;
        for (let i = 2; i <= n; i++) {
            if (i % 2 === 0) {
                nums[i] = nums[i / 2];
            } else {
                nums[i] = nums[Math.floor(i / 2)] + nums[Math.floor(i / 2) + 1];
            }
            if (nums[i] > ans) ans = nums[i];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We fill the array of size n+1 in a single pass.
  • 🧺 Space complexity: O(n) — We use an array of size n+1 to store the sequence.