LeetCode: 300번 (Longest Increasing Subsequence) [JAVA]

문제 링크

https://leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 nums 배열 길이만큼의 dp용 배열 초기화, 마지막 요소는 값을 1로 초기화 (가질 수 있는 최대 길이가 1이기 때문)
2. 배열의 끝에서부터 앞으로 for문을 돌며, 해당 요소보다 뒤에 있는 요소 중에 nums 값도 크고 dp값도 최대인 값을 찾아, 현재 dp 위치에 해당 값 + 1 저장
3. 다시 전체 dp 배열을 돌며 최대 길이를 찾아 반환

 단순히 완전탐색으로 각 위치에서 시작하는 최대 길이의 LIS를 찾아 반환하려고 하면 너무 큰 복잡도가 일어나기에, dp를 활용해 이전 탐색의 결과를 최대한 활용해야 한다. 그렇기 때문에 주어진 nums 배열 길이만큼의 dp용 배열을 생성한 후, dp용 배열 마지막 요소의 값을 1로 초기화한다. 이는 dp를 특정 위치의 요소에서 시작하는 최대 LIS의 길이를 찾을 때 그보다 뒤에 있는 배열 요소들 중 현 위치 값보다 크면서 최대 LIS 길이를 찾아, 그 결과 값의 +1을 현 위치의 최대 LIS로 저장하기 때문에 마지막 요소의 경우 최대 길이가 1이다.

 그런 다음 배열의 끝에서부터 앞으로 for문을 돌며, 해당 요소보다 뒤에 있는 요소 중에 nums 값도 크고 dp값도 최대인 값을 찾아, 현재 dp 위치에 해당 값 + 1 저장한다. 그런 다음 다시 전체 dp 배열을 돌며 최대 길이를 찾아 반환하면 된다.

 

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];//dp용 배열
        dp[dp.length - 1] = 1;//nums 배열의 마지막 요소 -> 길이가 1
        int answer = 1;

        for (int i = nums.length - 2; i >= 0; i--) {//마지막의 앞에서부터 맨앞까지
            dp[i] = 0;
            int maxIndex = i;

            for (int j = i + 1; j < nums.length; j++) {//i부터 마지막사이
                if (nums[i] < nums[j] && dp[maxIndex] < dp[j]) {//i보다 값이 크며 dp값이 최대인 것 찾기
                    maxIndex = j;
                }
            }

            dp[i] = dp[maxIndex] + 1;//해당 dp값 초기화
        }

        for (int i = 0; i < dp.length; i++) {//전체에서 dp 최대 값 찾기
            answer = Math.max(answer, dp[i]);
        }

        return answer;
    }
}

결과