This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

describe

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​​​.

Example 1:

Input: n = 7 Output: 3 Explanation: According to the given rules: nums[0] = 0 nums[1] = 1 nums[(1 * 2) = 2] = nums[1] = 1 nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2 nums[(2 * 2) = 4] = nums[2] = 1 nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3 nums[(3 * 2) = 6] = nums[3] = 2 nums[(3 * 2) Hence, the maximum is 3; Hence, the maximum is 3; Hence, the maximum is 3; Hence, the maximum is 3; Hence, the maximum is 3; Hence, the maximum is 3; Hence, the maximum is 3.Copy the code

Example 2:

Input: n = 2
Output: 1
Explanation: According to the given rules, the maximum between nums[0], nums[1], and nums[2] is 1.
Copy the code

Example 3:

Input: n = 3
Output: 2
Explanation: According to the given rules, the maximum between nums[0], nums[1], nums[2], and nums[3] is 2.
Copy the code

Note:

0 <= n <= 100
Copy the code

parsing

Given a number n, generate a list of n+1 numbers and find the maximum value. The procedure for generating the list NUMs is as follows:

  • When the index is 0, the value of this position is 0
  • When the index is 1, this position has a value of 1
  • Nums [I //2] for an even index I
  • Nums [I //2]+nums[I //2+1]

answer

class Solution(object):
    def getMaximumGenerated(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0:
            return 0
        if n==1:
            return 1
        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)
        	      
		
Copy the code

The results

Runtime: 10 ms, the linked list for the linked node gets Maximum in Generated Array. Submissions in the linked list for Get Maximum in Generated ArrayCopy the code

parsing

In addition, you can solve it recursively. Same idea. If n is odd, CAL (p)+ CAL (p+1) is obtained. If n is even, CAL (p) is obtained. At the end of recursion, the result can be obtained. Each element is a list of the results obtained by the end of the recursion, which is then maximized by the Max function.

answer

class Solution(object):
    def getMaximumGenerated(self, n):
        """
        :type n: int
        :rtype: int
        """
        def cal(n):
            if n <= 1: return n
            p = n // 2
            return cal(p) + cal(p + 1) if n%2 else cal(p)
        return max(cal(i) for i in range(n + 1))
Copy the code

The results

Runtime: 35 ms, the linked list for each node in the linked list. Each node in the linked list has the same length as the Generated Array.Copy the code

Link: leetcode.com/problems/ge…

Your support is my greatest motivation