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

Posted on | In
Words count in article: 345 | Reading time ≈ 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
3
4
5
6
7
8
9
10
11
12
输入：n = 7
输出：3
解释：根据规则：
  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 = 3
因此，nums = [0,1,1,2,1,3,2,3]，最大值 3

示例2：

1
2
3
输入：n = 2
输出：1
解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1

示例3：

1
2
3
输入：n = 3
输出：2
解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2

提示：

  • 0 <= n <= 100

解法一：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int getMaximumGenerated(int n) {
        if (0 == n) {
            return 0;
        }
        if (2 >= n) {
            return 1;
        }

        int max = -1;
        int[] result = new int[n + 1];
        result[1] = 1;
        int half = (n + 1) / 2;
        for (int i = 0;i <= half;i++) {
            int even = 2 * i;
            if (even < result.length) {
                result[2 * i] = result[i];
            }
            
            int odd = even + 1;
            if (odd < result.length) {
                result[2 * i + 1] = result[i] + result[i + 1];
            }
        }
        for (int num : result) {
            max = Math.max(num, max);
        }
        return max;
    }
0%