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

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

• nums[0] = 0
• nums[1] = 1
• 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
• 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大 值。

1示例 1：
2输入：n = 7
3输出：3
4解释：根据规则：
5  nums[0] = 0
6  nums[1] = 1
7  nums[(1 * 2) = 2] = nums[1] = 1
8  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
9  nums[(2 * 2) = 4] = nums[2] = 1
10  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
11  nums[(3 * 2) = 6] = nums[3] = 2
12  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
13因此，nums = [0,1,1,2,1,3,2,3]，最大值 3
14
15示例 2：
16输入：n = 2
17输出：1
18解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1
19
20示例 3：
21输入：n = 3
22输出：2
23解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2
24 
25提示：
260 <= n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/get-maximum-in-generated-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

1class Solution {
2   
3   
4public:
5    int getMaximumGenerated(int n) {
6   
7   
8        if(n <= 1) return n;
9        vector<int> arr(n+1);
10        arr[0] = 0;
11        arr[1] = 1;
12        int ans = 0;
13        for(int i = 1; i <= n; i++)
14        {
15   
16   
17            if(2*i >= 2 && 2*i <= n)
18            {
19   
20   
21                arr[2*i] = arr[i];
22                ans = max(ans, max(arr[i], arr[2*i]));
23            }
24            if(2*i+1 >= 2 && 2*i+1 <= n)
25            {
26   
27   
28                arr[2*i+1] = arr[i]+arr[i+1];
29                ans = max(ans, max(arr[i], arr[2*i+1]));
30            }
31            else
32                break;
33        }
34        return ans;
35    }
36};

0 ms 6.7 MB

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！