Get Maximum in Generated Array
Problem
An array nums of length n + 1 is generated by: nums[0] = 0, nums[1] = 1; for 2 ≤ 2i ≤ n, nums[2i] = nums[i]; for 2 ≤ 2i + 1 ≤ n, nums[2i + 1] = nums[i] + nums[i + 1]. Return the maximum value in nums.
n = 73def get_maximum_generated(n):
if n == 0:
return 0
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i // 2] if i % 2 == 0 else dp[i // 2] + dp[i // 2 + 1]
return max(dp)function getMaximumGenerated(n) {
if (n === 0) return 0;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = i % 2 === 0 ? dp[i / 2] : dp[(i - 1) / 2] + dp[(i - 1) / 2 + 1];
}
return Math.max(...dp);
}class Solution {
public int getMaximumGenerated(int n) {
if (n == 0) return 0;
int[] dp = new int[n + 1];
dp[1] = 1;
int best = 1;
for (int i = 2; i <= n; i++) {
dp[i] = i % 2 == 0 ? dp[i / 2] : dp[i / 2] + dp[i / 2 + 1];
best = Math.max(best, dp[i]);
}
return best;
}
}int getMaximumGenerated(int n) {
if (n == 0) return 0;
vector<int> dp(n + 1, 0);
dp[1] = 1;
int best = 1;
for (int i = 2; i <= n; i++) {
dp[i] = i % 2 == 0 ? dp[i / 2] : dp[i / 2] + dp[i / 2 + 1];
best = max(best, dp[i]);
}
return best;
}Explanation
The array is defined by a recurrence, so we just follow the rules and build it from the bottom up, exactly like filling a DP table. Every entry depends only on smaller indices, which are already computed.
The two base cases are dp[0] = 0 and dp[1] = 1. For any later index i we split on parity: if i is even, dp[i] = dp[i/2]; if i is odd, dp[i] = dp[i/2] + dp[i/2 + 1] (integer division).
Reading the rule for 2i and 2i + 1 in reverse gives exactly this: an even index i copies the value at i/2, and an odd index sums the two parents around i/2.
We fill dp once and track the largest value. Because each cell is a couple of lookups and an add, the whole array is built in linear time.
Example: for n = 7 we get dp = [0,1,1,2,1,3,2,3]. The biggest entry is 3, so the answer is 3.