Leetcode 1646. Get Maximum in Generated Array

Tyan

发布于 2021-07-01 10:30:36

2660

发布于 2021-07-01 10:30:36

文章被收录于专栏：SnailTyan

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Version 1

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        maximum = 1
        nums = [0 for _ in range(n+1)]
        nums[1] = 1
        for k in range(2, n + 1):
            i = k // 2 
            if k % 2 == 0:
                nums[k] = nums[i]
            else:
                nums[k] = nums[i] + nums[i+1]
            maximum = max(maximum, nums[k])
        return maximum

Version 2

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        maximum = 1
        nums = [0, 1]
        for k in range(2, n + 1):
            i = k // 2 
            if k % 2 == 0:
                current = nums[i]
            else:
                current = nums[i] + nums[i+1]
            nums.append(current)
            maximum = max(maximum, nums[k])
        return maximum