获取生成数组中的最大值

难度: Easy

给你一个整数 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：

输入：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：

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

示例 3：

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

提示：

0 <= n <= 100

Submission

运行时间: 16 ms

内存: 16.1 MB

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n<2:
            return n
        dp=[0]*(n+1)
        dp[0]=0
        dp[1]=1
        Maxdp=dp[1]
        for i in range(2,len(dp)):
            if i%2:
                dp[i]=dp[(i+1)//2]+dp[(i-1)//2]
            else:
                dp[i]=dp[i//2]
            Maxdp=max(Maxdp,dp[i])
        return Maxdp

Explain

此题解使用动态规划的方法来生成数组 nums，并实时跟踪最大值。数组 dp 初始化为长度 n+1 的全0数组，其中 dp[0]=0 和 dp[1]=1 是初始条件。接着，从 i=2 开始迭代至 n，根据 i 的奇偶性使用不同的规则更新 dp[i]。如果 i 是偶数，根据规则 dp[i] = dp[i//2]；如果是奇数，则 dp[i] = dp[(i+1)//2] + dp[(i-1)//2]。在每次更新 dp[i] 之后，还会更新 Maxdp 来保持记录数组中的最大值。最终，返回 Maxdp 作为结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n < 2:  # 如果 n 小于 2，直接返回 n
            return n
        dp = [0] * (n + 1)  # 初始化长度为 n+1 的数组 dp
        dp[0] = 0  # 根据规则设置 dp[0]
        dp[1] = 1  # 根据规则设置 dp[1]
        Maxdp = dp[1]  # 初始化最大值变量为 dp[1]
        for i in range(2, len(dp)):  # 从 2 遍历到 n
            if i % 2:  # 如果 i 是奇数
                dp[i] = dp[(i + 1) // 2] + dp[(i - 1) // 2]  # 根据规则计算 dp[i]
            else:  # 如果 i 是偶数
                dp[i] = dp[i // 2]  # 根据规则计算 dp[i]
            Maxdp = max(Maxdp, dp[i])  # 更新最大值
        return Maxdp  # 返回最大值

Explore

在初始化阶段，dp数组的长度被设置为n+1是为了保证数组能够容纳从0到n所有的索引。由于dp数组是用来存储每个索引对应的计算值，如果设置长度为n，那么索引n将会越界，因为数组索引是从0开始的。因此，为了方便直接使用索引值作为数组的索引，并避免越界错误，选择将dp数组的长度设置为n+1。

题解中使用不同的更新规则是基于动态规划的设计，它模拟了一个特定的数列生成规则。当i是偶数时，dp[i]的值是由dp[i/2]直接得来，这是因为偶数可以直接除以2而不改变整数性质。而当i是奇数时，dp[i]的值是dp[(i+1)/2]和dp[(i-1)/2]的和，这模拟了在奇数位置上的值由其相邻的偶数位置的值组合而成。这种设计是为了根据i的属性（奇偶性）有效地构造出整个数组。

使用Maxdp变量来实时记录最大值的优势在于效率。通过这种方式，我们可以在构建数组的同时跟踪最大值，避免了构建完整个数组后还需要再次遍历整个数组来找出最大值，从而减少了时间复杂度。然而，这种方法的劣势可能在于需要额外的操作来更新Maxdp，这在某些情况下可能稍微增加了每次迭代的计算负担。但总的来说，这种方法更适合实时或一次性处理的场景，可以有效提高总体效率。

在题解说明中，对于边界条件直接返回n的处理方式主要适用于n为0或1的情况，因为在这个特定问题中，dp数组的定义和逻辑是基于非负整数的序列。如果n是负数或非整数，这种处理方法在逻辑上并不适合，因为题目设定和dp数组的构建都是针对非负整数序列的。因此，对于负数或非整数的输入，应该考虑抛出错误或返回不合适的输入提示，而不是简单地返回n。