99클럽 코테 스터디 29일차 TIL + 오늘의 학습 키워드

☑️ 문제(Leetcode): 300. Longest Increasing Subsequence

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

 

☑️ Code: DP로 풀기

class Solution {
    public int lengthOfLIS(int[] nums) {
        int answer = 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j] && dp[i] <= dp[j]) {
                    dp[i] = dp[j] + 1;
                }
                answer = Math.max(dp[i], answer);
            }
        }

        return answer;
    }
}

DP code로 풀었을 경우 결과

 

찾아보니, 이분탐색으로 푸는 방법도 있었다.