LeetCode 1646: Get Maximum in Generated Array
Problem Description
Explanation
To solve this problem, we can simulate the generation of the array nums according to the given rules while keeping track of the maximum value encountered. We initialize the array nums with the first two elements [0, 1]. Then we iterate over the range [2, n] and update the array based on the rules. Finally, we return the maximum value in the array.
- Time complexity: O(n)
- Space complexity: O(n)
Solutions
class Solution {
public int getMaximumGenerated(int n) {
if (n == 0) {
return 0;
}
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
int max = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
nums[i] = nums[i / 2];
} else {
nums[i] = nums[i / 2] + nums[i / 2 + 1];
}
max = Math.max(max, nums[i]);
}
return max;
}
}Loading editor...