[LeetCode] Get Maximum in Generated Array

아르당·2026년 6월 7일

LeetCode

목록 보기
347/602
post-thumbnail

문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

정수 n이 주어진다. 길이가 n + 1인 0부터 시작하는 정수 배열 nums는 다음과 같은 방법으로 생성한다.

  • nums[0] = 0
  • nums[1] = 1
  • nums[2 * i] = nums[i] (2 <= 2 * i <= n)
  • nums[2 * i + 1] = nums[i] + nums[i + 1] (2 <= 2 * i + 1 <= n)

배열 nums에서 가장 큰 정수를 반환해라.

Example

#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이다.

Constraints

  • 0 <= n <= 100

Solved

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;
    }
}
profile
내 마음대로 코드 작성하는 세상

0개의 댓글