99클럽 코테 스터디 29일차 TIL - [LeetCode] Longest Increasing Subsequence (Java)

📌 오늘의 학습 키워드

[LeetCode] Longest Increasing Subsequence (Java)
https://leetcode.com/problems/longest-increasing-subsequence/description/

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 정수 배열 nums[]
출력 : 가장 긴 증가하는 수열의 길이

가능한 시간복잡도

O(n^2)

알고리즘 선택

dp

📌 코드 설계하기

1. dp 배열을 생성해 각 위치에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 저장한다. 각 요소는 최소 자기 자신만 포함하는 LIS를 가질 수 있으므로 초기값은 1이다.
2. 중첩 반복문을 통해 dp를 구현한다.
3. nums[i] > nums[j]라면, nums[i]는 nums[j] 뒤에 올 수 있으므로 dp[i]를 갱신한다. 이때 dp[i]는 dp[j] + 1과 현재 dp[i] 중 최대값으로 설정한다.
4. 외부 루프가 실행될 때마다 maxLength를 dp[i]와 비교하여 갱신해 가장 긴 LIS의 길이를 구한다.
5. maxLength를 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.Arrays;

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);  // 각 요소는 최소 자기 자신만 포함하는 LIS를 가지므로 초기값은 1

        int maxLength = 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }
}