Problem Description

The "Get Maximum in Generated Array" problem asks you to generate an array nums of length n + 1 using the following rules:

• nums[0] = 0
• nums[1] = 1 (if n >= 1)
• For all 2 <= 2 * i <= n, nums[2 * i] = nums[i]
• For all 2 <= 2 * i + 1 <= n, nums[2 * i + 1] = nums[i] + nums[i + 1]

Your task is to generate the array nums based on n and return the maximum integer in the array.

Constraints:

• 0 <= n <= 100

Thought Process

At first glance, this problem appears to require simulating the array generation process exactly as described. The rules are recursive and depend on previously computed values, so we need to build up the nums array step by step.

A brute-force approach would be to follow the rules literally for every index from 2 up to n. However, since each value depends only on earlier values, we can build the array in a single pass from 0 to n.

It is important to note that the array can be built efficiently because each value at index i only depends on values at indices less than i. This means we do not need to recompute or backtrack, and a simple loop will suffice. Once the array is built, finding the maximum is a standard operation.

Solution Approach

To solve this problem efficiently, we proceed as follows:

1. Initialization:
   • Create an array nums of size n + 1 and set nums[0] = 0.
   • If n >= 1, set nums[1] = 1.
2. Array Generation:
   • 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].
3. Result:
   • Return the maximum value in nums.

The design is straightforward because the dependencies are clearly defined and there are no overlapping subproblems or need for memoization beyond the current array.

Example Walkthrough

Let's walk through an example with n = 7:

• nums[0] = 0
• nums[1] = 1
• nums[2] = nums[1] = 1 (since 2 is even)
• nums[3] = nums[1] + nums[2] = 1 + 1 = 2 (since 3 is odd)
• nums[4] = nums[2] = 1 (since 4 is even)
• nums[5] = nums[2] + nums[3] = 1 + 2 = 3 (since 5 is odd)
• nums[6] = nums[3] = 2 (since 6 is even)
• nums[7] = nums[3] + nums[4] = 2 + 1 = 3 (since 7 is odd)

The final nums array is: [0, 1, 1, 2, 1, 3, 2, 3]. The maximum value is 3.

Time and Space Complexity

Brute-force Approach: If you tried to recursively compute each value from scratch, you might have exponential time due to recomputation. However, with the rules as given, a brute-force implementation is still linear because each value is computed once.

Optimized Approach:

• Time Complexity: O(n) — We iterate from 2 to n and perform a constant amount of work for each index.
• Space Complexity: O(n) — We store n + 1 integers in the nums array.

This is optimal for the problem as stated.

Code Implementation

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        nums = [0] * (n + 1)
        nums[0] = 0
        if n >= 1:
            nums[1] = 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]
        return max(nums)
      

class Solution {
public:
    int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        vector<int> nums(n + 1, 0);
        nums[0] = 0;
        if (n >= 1) nums[1] = 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];
        }
        return *max_element(nums.begin(), nums.end());
    }
};
      

class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        if (n >= 1) nums[1] = 1;
        int max = 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] > max) max = nums[i];
        }
        return max;
    }
}
      

var getMaximumGenerated = function(n) {
    if (n === 0) return 0;
    let nums = new Array(n + 1).fill(0);
    nums[0] = 0;
    if (n >= 1) nums[1] = 1;
    let max = 1;
    for (let i = 2; i <= n; i++) {
        if (i % 2 === 0) {
            nums[i] = nums[Math.floor(i / 2)];
        } else {
            nums[i] = nums[Math.floor(i / 2)] + nums[Math.floor(i / 2) + 1];
        }
        if (nums[i] > max) max = nums[i];
    }
    return max;
};
      

Summary

The "Get Maximum in Generated Array" problem is a classic example of building an array using defined recurrence rules and then extracting a property (the maximum). By following the rules in order, we can efficiently generate the array in linear time and space. The key insight is that each value depends only on previously computed values, making a single-pass solution both correct and optimal. This approach is elegant because it directly mirrors the problem statement and leverages dynamic programming principles without unnecessary complexity.