# Leetcode 1646. Get Maximum in Generated Array

## 題解

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        # Time complexity: O(n)
        # Space complexity: O(n)
        if n == 0:
            return 0
        output = 1
        nums = [0] * (n+1)
        nums[1] = 1
        for i in range(2, n+1):
            nums[i] = nums[i//2] + (i % 2) * nums[i//2+1]
            output = max(output,nums[i])
        return output