“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

The title

I give you an integer n. Generate an array nums of length n + 1 as follows:

  • 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

Returns the maximum value in the generated array NUMs.

Example 1:

Input: n = 7 Output: 3 Description: According to the 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) + 1 = 7] = nums[3] + NUMs [4] = 2 + 1 = 3Copy the code

Example 2:

Input: n = 2 Output: 1 Description: According to the rules, the maximum value of nums[0], NUMs [1], and NUMs [2] is 1Copy the code

Example 3:

Input: n = 3 Output: 2 Description: According to the rules, the maximum value of nums[0], NUMs [1], NUMs [2], and nums[3] is 2Copy the code

Their thinking

According to the passage, we can deduce the following rules:

  1. When I is odd, nums[I] = nums[I /2] + nums[I /2+1];
  2. When I is even, nums[I] = nums[I /2];

If I is even, I %2 is 0, and if I %2 is odd, I %2 is 1.

Code implementation

class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }

        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int max = 1;
        for (int i = 2; i <= n; i++) {
            nums[i] = nums[i/2] + (i%2)*nums[i/2 + 1];
            if(nums[i] > max) { max = nums[i]; }}returnmax; }}Copy the code

The last

Time complexity: O(n);

Space complexity: O(n);

Previous articles:

  • Binary tree brush summary: binary search tree properties
  • Binary tree summary: binary tree properties
  • Binary tree summary: binary tree modification and construction
  • StoreKit2 smells this good? Yeah, I tried it. It smells good
  • After reading this article, I am no longer afraid of being asked how to construct a binary tree.
  • The game guys are trying to get people to pay again. That’s bad!
  • Take you rolled a netease holding cloud music home | adapter
  • Netease Cloud Music Home Page (3)
  • Netease Cloud Music Home Page (2)
  • Netease Cloud Music Home Page (a)
  • Does the code need comments? Write and you lose
  • I would not study in Codable for a long time. They are for fun
  • IOS handles web data gracefully. Do you really? Why don’t you read this one
  • UICollectionView custom layout! This one is enough

Please drink a cup ☕️ + attention oh ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. Follow the public number – HelloWorld Jie Shao, the first time push new posture

Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~ **