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

原题链接

题目描述

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

• $nums[0] = 0$

• $nums[1] = 1$

• 当 $2 \le 2 * i \le n$ 时，$nums[2 * i] = nums[i]$

• 当 $2 \le 2 * i + 1 \le n$ 时，$nums[2 * i + 1] = nums[i] + nums[i + 1]$

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

数据范围

$0 \le n \le 100$

样例

输入样例1：

n = 7

输出样例1：

3

样例1解释：

根据规则：
$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：

n = 2

输出样例2：

1

样例2解释：

根据规则，$nums[0]$、$nums[1]$ 和 $nums[2]$ 之中的最大值是 $1$

输入样例3：

n = 3

输出样例3：

2

思路

简单模拟，返回最大值。不过可以给简化一下递推式。

当 $i \ge 2$。

若 $i$ 为奇数，则：$a[i * 2 + 1] = a[i] + a[i + 1]$ ，可以变成 $a[i] = a[\lfloor\frac{i}{2}\rfloor] + a[\lfloor\frac{i}{2}\rfloor + 1]$。

若 $i$ 为偶数，则：$a[i * 2] = a[i]$ ，可以变成 $a[i] = a[\frac{i}{2}]$。

结合一下：$a[i] = a[\lfloor\frac{i}{2}\rfloor] + i \ \% \ 2 * a[\lfloor\frac{i}{2}\rfloor + 1]$。

代码

C++

const int N = 105;
int a[N];

class Solution {
public:
    int getMaximumGenerated(int n) {
        a[0] = 0;
        a[1] = 1;

        int res = a[n];
        for ( int i = 2; i <= n; i ++ )
        {
            a[i] = a[i / 2] + i % 2 * a[i / 2 + 1];
            res = max(res, a[i]);
        }
        return res;
    }
};

Java

class Solution {
    public int getMaximumGenerated(int n) {
        int a[] = new int[n + 2];
        a[0] = 0;
        a[1] = 1;
        
        int res = a[n];
        for ( int i = 2; i <= n; i ++ )
        {
            a[i] = a[i / 2] + i % 2 * a[i / 2 + 1];
            res = Math.max(res, a[i]);
        }
        return res;
    }
}