https://leetcode.com/problems/get-maximum-in-generated-array

In this problem you just need to do what is asked: if we have even and odd indexes, generate data in correct way. There is a couple of small tricks to make your code cleaner:

  1. Create nums = [0] * (n + 2) to handle case n = 0.
  2. Use ` nums[i] = nums[i//2] + nums[(i//2)+1] * (i%2)` to handle both cases of even and odd indexes
  3. Finally, return maximum among first n + 1 elements.

Complexity: time and space complexity is O(n).

Discussion As it is with given solution problem just do not have any idea behind. I think there should be O(log n) solution, I am thinking about right now.

class Solution:
    def getMaximumGenerated(self, n):
        nums = [0]*(n+2)
        nums[1] = 1
        for i in range(2, n+1):
            nums[i] = nums[i//2] + nums[(i//2)+1] * (i%2)
    
        return max(nums[:n+1])

If you like the solution, you can upvote it on leetcode discussion section: Problem 1646