99클럽 코테 스터디 29일차 TIL < Longest Increasing Subsequence >

오늘의 문제

 

 

	Given an integer array nums, return the length of the longest strictly increasing 
			subsequence
			.
			Example 1:

			Input: nums = [10,9,2,5,3,7,101,18]
			Output: 4
			Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
			Example 2:

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

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

			Constraints:

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

 

학습 키워드

 

---

 

이분 탐색

---

 

문제 풀이

1. 배열의 모든 원소를 1로 초기화
2. 현재 위치의 왼쪽 원소 값을 보고 증가하면 비교하고 업데이트
3. 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;
    }
}

 

 
 
오늘의 회고