Get Maximum in Generated Array - Video Solutions

Problem Overview: You build an integer array nums using a specific recurrence rule. Starting with nums[0] = 0 and nums[1] = 1, every index i from 2 to n is derived from earlier values. The task is to generate this array up to n and return the maximum value that appears in it.

Approach 1: Iterative Simulation (Time: O(n), Space: O(n))

The most direct method is to simulate the construction of the array exactly as defined. Allocate an array nums of size n + 1. For every index i from 2 to n, apply the rule: if i is even, set nums[i] = nums[i / 2]; if i is odd, set nums[i] = nums[i / 2] + nums[i / 2 + 1]. Each value depends only on previously computed indices, so a single forward pass works. After building the array, scan it to find the maximum value. This is a classic array construction problem combined with straightforward simulation. The time complexity is O(n) for building the array and scanning it, and the space complexity is O(n) for storing the generated values.

Approach 2: Space-Optimized Iterative Approach (Time: O(n), Space: O(n) with O(1) extra)

You can remove the extra pass used to compute the maximum by tracking it while generating the array. As each nums[i] is computed, update a running maxValue. The recurrence remains the same, but the algorithm performs both generation and maximum tracking in a single loop. This eliminates the need for a second traversal and keeps additional memory usage constant beyond the required array storage. The algorithm still runs in O(n) time and uses O(n) space for the generated array, but only O(1) extra variables.

Recommended for interviews: The iterative simulation is what interviewers expect. It shows you can translate a recurrence definition directly into code and reason about dependencies between indices. Tracking the maximum during construction is a small but practical optimization that demonstrates attention to efficiency while keeping the implementation simple.