Code Logo

Get Maximum in Generated Array

Published at24 Jul 2026
Created by
Easy 1 views
Like0

You are given an integer n. You generate an array nums of length n+1 using the following rules: nums[0] = 0, nums[1] = 1. For even i (2<= i <= n): nums[i] = nums[i / 2]. For odd i: nums[i] = nums[i // 2] + nums[i // 2 + 1]. Return the maximum value in the generated array.

This problem combines DP array generation with a max-tracking step. The recurrence uses previously computed values at floor(i/2) and floor(i/2)+1, which are always smaller indices than i. This ensures all dependencies are already computed when processing i in increasing order.

The DP table is built sequentially from 0 to n. For each even index, the value equals the value at half the index. For each odd index, it is the sum of two adjacent values at half the index (floor division). The maximum value seen so far is tracked and returned at the end.

Edge cases include n = 0 (return 0), n = 1 (return 1), and n = 2 (return 1 from nums[1] = 1).

The array generation recurrence uses the binary representation of indices: even indices reference the value at half the index, while odd indices sum two adjacent values at floor(i/2). This pattern is related to the Calkin-Wilf tree in number theory.

Example Input & Output

Example 1
Input
7
Output
3
Explanation

nums=[0,1,1,2,1,3,2,3], max=3

Example 2
Input
3
Output
2
Explanation

nums=[0,1,1,2], max=2

Example 3
Input
2
Output
1
Explanation

nums=[0,1,1], max=1

Example 4
Input
5
Output
3
Explanation

nums=[0,1,1,2,1,3], max=3

Example 5
Input
0
Output
0
Explanation

nums=[0], max=0

Algorithm Flow

Recommendation Algorithm Flow for Get Maximum in Generated Array

Solution Approach

Generate an array nums of length n+1 following rules: nums[0]=0, nums[1]=1. For even i, nums[i]=nums[i/2]. For odd i, nums[i]=nums[i/2]+nums[i/2+1]. Return the maximum value in the generated array. This is a constructive DP where each value depends on previously computed values at halved indices.

function getMaximumGenerated(n) {
  if (n === 0) return 0;
  var nums = Array(n + 1).fill(0);
  nums[1] = 1;
  var maxVal = 1;
  for (var i = 2; i <= n; i++) {
    if (i % 2 === 0) nums[i] = nums[i / 2];
    else nums[i] = nums[(i - 1) / 2] + nums[(i - 1) / 2 + 1];
    if (nums[i] > maxVal) maxVal = nums[i];
  }
  return maxVal;
}

For even indices, the value equals the value at half the index. For odd indices, it sums two adjacent values at half the index. The maximum is tracked during generation to avoid a second pass.

Time complexity is O(n), space complexity is O(n).

Best Answers

java
class Solution {
    public int solution(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        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 nums[i] = nums[i / 2] + nums[i / 2 + 1];
            if (nums[i] > maxVal) maxVal = nums[i];
        }
        return maxVal;
    }
}