문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음
정수 n이 주어진다. 길이가 n + 1인 0부터 시작하는 정수 배열 nums는 다음과 같은 방법으로 생성한다.
배열 nums에서 가장 큰 정수를 반환해라.
#1
Input: n = 7
Output: 3
Explanation: 주어진 규칙에 따르면:
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]이고, 가장 큰 수는 max(0, 1, 1, 2, 1, 3, 2, 3) = 3이다.
#2
Input: n = 2
Output: 1
Explanation: 주어진 규칙에 따르면, nums = [0, 1, 1]이다. 가장 큰 수는 max(0, 1, 1) = 1이다.
#3
Input: n = 3
Output: 2
Explanation: 주어진 규칙에 따르면, nums = [0, 1, 1, 2]이다. 가장 큰 수는 max(0, 1, 1, 2) = 2이다.
class Solution {
public int getMaximumGenerated(int n) {
if(n == 0 || n == 1){
return n;
}
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
int max = 1;
for(int i = 1; (2 * i + 1) <= n; i++){
nums[2 * i] = nums[i];
nums[2 * i + 1] = nums[i] + nums[i + 1];
max = Math.max(max, nums[2 * i + 1]);
}
return max;
}
}