🔥[99클럽 코테 스터디] 29일차 TIL - Longest Increasing Subsequence

⏳문제

Given an integer array nums, return the length of the largest strictly increaing subsequence.

🚨제한 사항

• 1 <= nums.length <= 2500
• $-10^4$ <= nums[i] <= $10^4$

📃입출력 예

입출력 예 #1

Input	Output
nums = [10,9,2,5,3,7,101,18]	4

Explanation : The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

입출력 예 #2

Input	Output
nums = [0,1,0,3,2,3]	4

입출력 예 #3

Input	Output
nums = [7,7,7,7,7,7,7]	1

---

✏️풀이

이 문제는 완전 탐색으로도 풀 수 있지만,
Dynamic Programming 기법을 사용하면 더 효율적이다.

Dynamic Programming 기법을 사용하기 위해 주어진 nums의 길이만큼의 dp배열을 하나 만들어 주어야 한다.
이 문제에서 dp배열의 역할은 i번째 숫자가 마지막 배열의 원소일 때, 그 배열에서 가장 긴 오름차순 수열의 길이를 저장하는 것이다.
그러면, 이전 탐색의 결과를 최대한 활용할 수가 있게 된다.

dp 배열 생성 및 초기화

// dp 배열 생성
int[] dp = new int[nums.length];

// dp 배열 초기화
for (int i = 0; i < dp.length; i++) {
	dp[i] = 1;
}

주어진 nums배열 길이만큼 dp 배열을 생성해 주고,
모든 원소를 1로 초기화 한다.

오름차순 순열의 길이 구하기

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

현재 위치 i에서 i보다 왼쪽에 있는 원소들의 dp[i] 값들을 확인 후,
nums[j] < nums[i]인 경우 원소값들을 비교하고, dp배열에 업데이트를 해 준다.

---

👾최종 코드

public static int lengthOfLIS(int[] nums) {
        int answer = 1;

         // dp 배열 생성
        int[] dp = new int[nums.length];

        // dp 배열 초기화
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }

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

        for (int i : dp) {
            answer = Math.max(answer, i);
        }


        return answer;
    }

---

🔗 문제 링크
💻Repository