[Java/Python3] leetcode 300. Longest Increasing Subsequence

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

Longest Increasing Subsequence - LeetCode

 

문제

가장 최장으로 증가하는 부분 수열의 길이를 구하는 문제. 

문제 조건에

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

으로 주어졌으니 2500 * 2500 = 6,250,000 으로 O(N^2) 으로 풀수있음을 알수 있다. 

 

풀이

dp[] 배열을 하나 만든다. 이때 이배열의 원소 dp[i] 의 뜻은 

dp[i]  == i 번째 숫자가 배열의 마지막 원소일때, 그 배열의 가장 긴 부분 증가 수열 길이 

이다. 우선 dp 배열의 모든 원소를 1로 초기화한 후 

현재 위치 i 에서 , i 보다 왼쪽에 있는 원소들의 dp[j] 값들을 보고 nums[i] > nums[j] 이면(증가하면) 원소값들을 비교하고 업데이트 해준다. 

 

참고

풀이 사진을 첨부한다. dp 배열 업데이트 과정을 시각화 하였으니 직접 그리기 귀찮으신 분들은 참고하시길. 

dp[i] 배열 을 최신화하는 전체과정.

 

코드

자바

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int len = nums.length;
        int longest = dp[0];
        for(int i =1  ;i < len ;i++){
            for(int j =0 ; j< i; j++ ){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
                    
            }
        }
        for(int x : dp)
            longest = Math.max(longest, x);
        return longest;
    }
}

파이썬

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for x in range(len(nums))]
        
        for i in range(len(nums)):
            for j in range(i):
                dp[i] = max(dp[i], dp[j]+1) if nums[j] < nums[i] else dp[i]
        ans = 1
        for x in dp:
            ans = max(ans,x)
        return ans