Domain 1EasyCORE

Get Maximum in Generated Array

The problem requires generating an array `nums` of length `n + 1` based on specific rules and then finding the maximum value in that array. The rules for generating the array are: - `nums[0] = 0` - `nums[1] = 1` - For even indices: `nums[2 * i] = nums[i]` - For odd indices: `nums[2 * i + 1] = nums[i] + nums[i + 1]`

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1646. Get Maximum in Generated Array

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 53.2%


Problem Breakdown

The problem requires generating an array nums of length n + 1 based on specific rules and then finding the maximum value in that array. The rules for generating the array are:

  • nums[0] = 0
  • nums[1] = 1
  • For even indices: nums[2 * i] = nums[i]
  • For odd indices: nums[2 * i + 1] = nums[i] + nums[i + 1]

The input is a single integer n, and the output is the maximum value in the generated array. The constraints are that 0 <= n <= 100.

Implicit constraints include:

  • If n is 0, the array will only contain one element [0].
  • If n is 1, the array will be [0, 1].

Intuition

A brute-force approach would involve generating the array and then iterating through it to find the maximum value. However, this approach is inefficient because it requires two passes over the array (one for generation and one for finding the maximum).

The key insight is that we can generate the array in a single pass while keeping track of the maximum value encountered so far. This reduces the time complexity from O(2n) to O(n).

Approach

  1. Initialize an empty list nums with size n + 1.
  2. Set the base cases: nums[0] = 0 and nums[1] = 1.
  3. Iterate through the array starting from index 2 up to n:
    • If the index is even, set nums[i] = nums[i // 2].
    • If the index is odd, set nums[i] = nums[i // 2] + nums[i // 2 + 1].
  4. Keep track of the maximum value encountered during the array generation.
  5. Return the maximum value.

Complexity Analysis

  • Time Complexity: O(n) because we iterate through the array once to generate it and find the maximum value.
  • Space Complexity: O(n) for storing the generated array.

Solution

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

Edge Cases Handled

  • n = 0: The array is [0], and the maximum value is 0.
  • n = 1: The array is [0, 1], and the maximum value is 1.
  • n = 2: The array is [0, 1, 1], and the maximum value is 1.
  • n = 3: The array is [0, 1, 1, 2], and the maximum value is 2.
  • n = 7: The array is [0, 1, 1, 2, 1, 3, 2, 3], and the maximum value is 3.

This solution efficiently generates the array and finds the maximum value in a single pass, adhering to the constraints and handling all edge cases.