Get Maximum in Generated Array — Problem & Solution
Get Maximum in Generated Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Get Maximum in Generated Array is an easy coding problem on arrays and simulation, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Build an array nums of length n + 1 by these rules:
nums[0] = 0nums[1] = 1(whenn >= 1)nums[2 * i] = nums[i]when2 <= 2 * i <= nnums[2 * i + 1] = nums[i] + nums[i + 1]when2 <= 2 * i + 1 <= n
Return the largest value in nums.
Example 1
Input: n = 7
Output: 3
Explanation: nums = [0,1,1,2,1,3,2,3], whose maximum is 3.
Example 2
Input: n = 2
Output: 1
Explanation: nums = [0,1,1].
Example 3
Input: n = 0
Output: 0
Constraints
0 <= n <= 100
Hints for Get Maximum in Generated Array
Hint 1
Every entry depends only on entries with smaller indices.
Hint 2
Fill the array from index 2 upwards, using
i / 2(andi / 2 + 1for oddi).Hint 3
Track the maximum as you go, and handle
n = 0before touchingnums[1].
How to solve Get Maximum in Generated Array
The recurrence only looks backwards — nums[i] uses indices around i / 2 — so filling the array left to right computes every value once.
Approach
- If
n == 0return 0. - Set
nums[0] = 0,nums[1] = 1,best = 1. - For
ifrom 2 ton: leth = i / 2; setnums[i] = nums[h]for eveni, otherwisenums[h] + nums[h + 1]; updatebest. - Return
best.
Why it works
For i >= 2, both h and h + 1 are smaller than i, so the values they need are already final when nums[i] is computed. Every entry is therefore exactly what the rules define, and the running maximum covers all of them.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- For
n = 0the array is just[0]; writingnums[1]would go out of bounds. - An odd index
2i + 1usesnums[i] + nums[i + 1], withi = (index - 1) / 2. - The maximum is not always at the last index —
n = 7peaks at index 5.
Reference solution
Python
def getMaximumGenerated(n: int) -> int:
if n == 0:
return 0
nums = [0] * (n + 1)
nums[1] = 1
for i in range(2, n + 1):
h = i // 2
nums[i] = nums[h] if i % 2 == 0 else nums[h] + nums[h + 1]
return max(nums)Java
public static int getMaximumGenerated(int n) {
if (n == 0) return 0;
int[] nums = new int[n + 1];
nums[1] = 1;
int best = 1;
for (int i = 2; i <= n; i++) {
int h = i / 2;
nums[i] = i % 2 == 0 ? nums[h] : nums[h] + nums[h + 1];
best = Math.max(best, nums[i]);
}
return best;
}C++
int getMaximumGenerated(int n) {
if (n == 0) return 0;
vector<int> nums(n + 1, 0);
nums[1] = 1;
int best = 1;
for (int i = 2; i <= n; i++) {
int h = i / 2;
nums[i] = i % 2 == 0 ? nums[h] : nums[h] + nums[h + 1];
best = max(best, nums[i]);
}
return best;
}JavaScript
var getMaximumGenerated = function(n) {
if (n === 0) return 0;
var nums = [0, 1], best = 1;
for (var i = 2; i <= n; i++) {
var h = Math.floor(i / 2);
nums.push(i % 2 === 0 ? nums[h] : nums[h] + nums[h + 1]);
if (nums[i] > best) best = nums[i];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays