Cinte's Leetcode Record
0%

1646. 获取生成数组中的最大值

Posted on Edited on In Disqus:
Symbols count in article: 668 Reading time ≈ 1 mins.

1646. 获取生成数组中的最大值

直接模拟生成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int getMaximumGenerated(int n) {
        if(n <= 1)
            return n;
        int ret = 0;
        vector<int> nums(n + 1, 0);
        nums[0] = 0;
        nums[1] = 1;
        for(int i = 1; i <= n / 2; ++i)
        {
            nums[2 * i] = nums[i];
            ret = max(ret, nums[2 * i]);
            if(2 * i + 1 <= n)
            {
                nums[2 * i + 1] = nums[i] + nums[i + 1];
                ret = max(nums[2 * i + 1], ret);
            }
        }
        return ret;
    }
};

合并奇数和偶数的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int getMaximumGenerated(int n) {
        if(n <= 1)
            return n;
        int ret = 0;
        vector<int> nums(n + 1, 0);
        nums[0] = 0;
        nums[1] = 1;
        for(int i = 2; i <= n; ++i)
        {
            nums[i] = nums[i / 2] + (i & 1) * nums[i / 2 + 1];
            ret = max(nums[i], ret);
        }
        return ret;
    }
};