# Get Maximum in Generated Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/get-maximum-in-generated-array)
Canonical: https://scaleengineer.com/dsa/problems/get-maximum-in-generated-array
**Data structures:** Array
---
## 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_the **maximum** integer in the array_ `nums`​​​.

**Example 1:**

**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:**

**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:**

**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`

# Approaches
## Naive Recursion
This approach directly translates the generation rules into a recursive function. To find the maximum, it iterates through all indices from 0 to `n` and calls the recursive function for each, finding the maximum value. This method is conceptually simple but highly inefficient.
**Time:** O(2^n). The number of recursive calls grows exponentially with `n`. This is because each call for an odd number `k` branches into two subproblems, and many subproblems (like `getValue(3)`) are re-calculated multiple times. · **Space:** O(log n). The space complexity is determined by the maximum depth of the recursion call stack. To compute `getValue(n)`, the recursion depth is proportional to `log n`.
**Pros:** Simple to write as it's a direct translation of the problem's mathematical definition.
**Cons:** Extremely inefficient due to massive re-computation of values for the same indices.; Will result in a 'Time Limit Exceeded' error on most platforms for `n` greater than about 30-40.
### Explanation
We define a function `getValue(i)` that computes `nums[i]` by strictly following the recurrence relation given in the problem. The base cases are `getValue(0) = 0` and `getValue(1) = 1`. For any other index `i`, the function calls itself with smaller indices (`i/2` or `i/2` and `i/2 + 1`). The main function then iterates from 0 to `n`, calling `getValue(i)` for each `i` and tracking the maximum value seen. This approach is very inefficient because it recomputes the values for the same indices multiple times. For instance, calculating `getValue(7)` and `getValue(6)` both require `getValue(3)`, which will be computed twice from scratch. This redundancy leads to an exponential number of calls.

```java
class Solution {
    public int getMaximumGenerated(int n) {
        if (n < 2) {
            return n;
        }
        int maxVal = 0;
        for (int i = 0; i <= n; i++) {
            maxVal = Math.max(maxVal, getValue(i));
        }
        return maxVal;
    }

    private int getValue(int k) {
        if (k == 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        if (k % 2 == 0) {
            return getValue(k / 2);
        } else {
            return getValue(k / 2) + getValue(k / 2 + 1);
        }
    }
}
```
### Algorithm
- The main function handles the base cases for `n < 2`.
- It initializes a variable `maxVal` to 0.
- It then iterates from `i = 0` to `n`.
- In each iteration, it calls a recursive helper function `getValue(i)` to compute the value of `nums[i]`.
- It updates `maxVal` with the maximum value seen so far.
- The `getValue(k)` function is defined as follows:
  - Base case: If `k` is 0, return 0. If `k` is 1, return 1.
  - Recursive step for even `k`: return `getValue(k / 2)`.
  - Recursive step for odd `k`: return `getValue(k / 2) + getValue(k / 2 + 1)`.

## Recursion with Memoization (Top-Down DP)
This approach improves upon the naive recursion by using memoization to avoid recomputing results for the same subproblems. It's a form of top-down dynamic programming. An auxiliary array is used to store the results of `nums[i]` once they are computed, so subsequent calls for the same index can return the stored value in constant time.
**Time:** O(n). Each value `nums[i]` for `i` from 0 to `n` is computed once. The main loop runs `n+1` times, and each call to `getValue` results in a constant number of operations (amortized) due to memoization. · **Space:** O(n). We need an array of size `n + 1` for the memoization table. The recursion stack depth contributes an additional O(log n), making the total space complexity O(n).
**Pros:** Efficient, as it solves the overlapping subproblems issue.; Guarantees that each state `nums[i]` is computed only once.; Maintains a clear mapping from the recurrence relation.
**Cons:** Slightly more complex to implement than naive recursion due to the memoization table.; Has the overhead of recursive function calls, which can be marginally slower than a pure iterative solution.
### Explanation
To fix the inefficiency of the naive recursive approach, we can store the results of `getValue(i)` in a memoization table (an array, `memo`). Before computing `getValue(i)`, we first check if the result is already in our table. If it is, we return it directly. If not, we compute it recursively as before, but we store the result in `memo[i]` before returning. This ensures that the value for each index `i` from 0 to `n` is calculated exactly once. This technique is known as top-down dynamic programming.

```java
class Solution {
    int[] memo;

    public int getMaximumGenerated(int n) {
        if (n < 2) {
            return n;
        }
        memo = new int[n + 1];
        java.util.Arrays.fill(memo, -1);
        
        int maxVal = 0;
        // We need to find the max in the entire generated array, not just nums[n]
        for (int i = 0; i <= n; i++) {
            maxVal = Math.max(maxVal, getValue(i));
        }
        return maxVal;
    }

    private int getValue(int k) {
        if (k == 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        if (memo[k] != -1) {
            return memo[k];
        }
        
        if (k % 2 == 0) {
            memo[k] = getValue(k / 2);
        } else {
            memo[k] = getValue(k / 2) + getValue(k / 2 + 1);
        }
        return memo[k];
    }
}
```
### Algorithm
- Handle base cases for `n < 2`.
- Create a memoization array `memo` of size `n + 1` and initialize it with a sentinel value (e.g., -1) to indicate that no value has been computed yet.
- The main function iterates from `i = 0` to `n`, calling a recursive helper `getValue(i, memo)` and updating the maximum value found.
- The `getValue(k, memo)` function works as follows:
  - If `k` is 0 or 1, return `k`.
  - If `memo[k]` is not the sentinel value, return it immediately.
  - Otherwise, compute the result based on whether `k` is even or odd, using recursive calls.
  - Store the computed result in `memo[k]` before returning it.

## Iterative Simulation (Bottom-Up DP)
This is the most efficient and straightforward approach, often called bottom-up dynamic programming. It simulates the generation process iteratively. We create an array to store the numbers and fill it from index 2 up to `n`, using the values that have already been computed. While filling the array, we keep track of the maximum value encountered.
**Time:** O(n). We iterate through the numbers from 2 to `n` once, and each calculation is a constant-time operation. · **Space:** O(n). An array of size `n + 1` is used to store the generated numbers.
**Pros:** Most efficient in terms of performance as it avoids recursion overhead.; Easy to understand and implement.; Optimal time and space complexity for this problem.
**Cons:** Requires O(n) extra space for the array, which is unavoidable for this problem but worth noting.
### Explanation
Instead of a top-down recursive approach, we can solve this problem iteratively from the bottom up. This avoids recursion overhead and is often more intuitive for simulation-style problems. We create an array `nums` of size `n + 1`. We know `nums[0]` and `nums[1]` from the problem description. We can then compute the rest of the values in order, from `nums[2]` up to `nums[n]`. When we compute `nums[i]`, the values it depends on (`nums[i/2]` and `nums[i/2 + 1]`) have already been computed because their indices are smaller than `i`. We maintain a variable to track the maximum value as we generate the array.

```java
class Solution {
    public int getMaximumGenerated(int n) {
        if (n <= 1) {
            return n;
        }
        
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        
        int maxVal = 1;
        
        for (int i = 2; i <= n; i++) {
            if (i % 2 == 0) {
                nums[i] = nums[i / 2];
            } else {
                // For odd i, integer division i/2 is the same as (i-1)/2
                nums[i] = nums[i / 2] + nums[i / 2 + 1];
            }
            maxVal = Math.max(maxVal, nums[i]);
        }
        
        return maxVal;
    }
}
```
### Algorithm
- Handle the base cases: if `n` is 0 or 1, return `n`.
- Create an integer array `nums` of size `n + 1`.
- Initialize the first two values based on the rules: `nums[0] = 0` and `nums[1] = 1`.
- Initialize a variable `maxVal` to 1, as this is the maximum for `n >= 1` so far.
- Iterate with an index `i` from 2 to `n`.
- Inside the loop, calculate `nums[i]` based on previously computed values:
  - If `i` is even, `nums[i] = nums[i / 2]`.
  - If `i` is odd, `nums[i] = nums[i / 2] + nums[i / 2 + 1]`.
- After computing `nums[i]`, update `maxVal = Math.max(maxVal, nums[i])`.
- After the loop finishes, return `maxVal`.

# Solutions
### Java

```java
class Solution {
public
  int getMaximumGenerated(int n) {
    if (n < 2) {
      return n;
    }
    int[] nums = new int[n + 1];
    nums[1] = 1;
    for (int i = 2; i <= n; ++i) {
      nums[i] = i % 2 == 0 ? nums[i >> 1] : nums[i >> 1] + nums[(i >> 1) + 1];
    }
    return Arrays.stream(nums).max().getAsInt();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getMaximumGenerated(int n) {
    if (n < 2) {
      return n;
    }
    int nums[n + 1];
    nums[0] = 0;
    nums[1] = 1;
    for (int i = 2; i <= n; ++i) {
      nums[i] = i % 2 == 0 ? nums[i >> 1] : nums[i >> 1] + nums[(i >> 1) + 1];
    }
    return *max_element(nums, nums + n + 1);
  }
};

```

### Python

```python
class Solution:
    def getMaximumGenerated(self, n: int) -> int: if n < 2: return n nums = [0] * (n + 1) nums[1] = 1 for i in range(2, n + 1): nums[i] = nums[i >> 1] if i % 2 == 0 else nums[i >> 1] + nums[(i >> 1) + 1] return max(nums)

```