Get Maximum in Generated Array

1646. Get Maximum in Generated Array You are given an integer n. An array nums of length n + 1 is generated in the following way:

nums[0] = 0
nums[1] = 1
nums[2 * i] = nums[i] when 2 <= 2 * i <= n
nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n
Return the maximum integer in the array nums​​​.

Solution - Simulation

1. Create the array.

2. Get the maximum element in the array.

def getMaximumGenerated(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n <= 1:
        return n
    nums = [0, 1]
    for i in range(2, n+1):
        if i % 2 == 0:
            nums.append(nums[i / 2])
        else:
            nums.append(nums[i / 2] + nums[i / 2 + 1])
    return max(nums)

Solution - Precompute

Reference

1. Compute the array for the first element.

2. Store the largest element up to i in nums[i].

3. Just retrieve from the array for all the following request.

int f[101] = { 0, 1, 0};
class Solution {
public:
    int getMaximumGenerated(int n) {
        if (f[2] == 0) {
            for (int i = 2; i <= 100; ++i)
                f[i] = i % 2 ? f[i / 2] + f[i / 2 + 1] : f[i / 2];
            for (int i = 2; i <= 100; ++i)
                f[i] = max(f[i], f[i - 1]);
        }
        return f[n];
    }
};