获取生成数组中的最大值
难度:
标签:
题目描述
代码结果
运行时间: 16 ms, 内存: 16.1 MB
/*
* Solution approach using Java Streams for generating the array and finding the maximum value:
* 1. Initialize an array of length n+1 with all zeros.
* 2. Set the first two values: nums[0] = 0 and nums[1] = 1.
* 3. Use IntStream to fill the array based on the given rules.
* 4. Use IntStream to find and return the maximum value in the array.
*/
import java.util.stream.IntStream;
public class Solution {
public int getMaximumGenerated(int n) {
if (n == 0) return 0;
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
IntStream.range(2, n + 1).forEach(i -> {
if (i % 2 == 0) {
nums[i] = nums[i / 2];
} else {
nums[i] = nums[i / 2] + nums[i / 2 + 1];
}
});
return IntStream.of(nums).max().orElse(0);
}
}
解释
方法:
此题解使用动态规划的方法来生成数组 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)
代码细节讲解
🦆
在初始化阶段,为什么选择将dp数组的长度设置为n+1而不是n?
▷🦆
题解中提到的动态规划在更新dp[i]时,为什么i的奇偶性会决定使用不同的更新规则?
▷🦆
解法中使用Maxdp变量来实时记录最大值,这种方法与在最后遍历dp数组寻找最大值相比,有什么优势或劣势?
▷🦆
在题解说明中,对于边界条件n小于2时直接返回n的处理方式,这是否适用于所有小于2的n值,包括负数或非整数?
▷