[LeetCode] Longest Increasing Subsequence

1. 문제 : https://leetcode.com/problems/longest-increasing-subsequence/

말그대로 증가하는 배열 찾기

 

2. 풀이

dp 문제

역순으로 돌면서 자신보다 큰 수의 dp 중 가장 큰값 +1을 dp에 저장

이때 증가하는 것을 신경 쓸 필요가 없는 이유 -> 시작부터 나보다 큰수를 dp에 저장해가며 반복문을 돌기때문에 해당 dp에 저장된 값 자체가 증가하는 경우의 수만 고려한 것이기 때문

 

나보다 큰 수 dp중 가장 큰 값을 고르는 이유? -> 계속 증가하는 값 중 가장 많은 경우의 수를 구해야하기 때문

 

ex)

숫자 2는 코인2 한번에 만들 수 있음 -> 이걸 어떻게 dp로 자동으로 하냐? -> dp[i-money즉 0]  +1 과 dp[i] 값 중 비교해서 넣으면됨

 

3. 코드

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {

        int len = nums.length;
        if(len == 1) return 1;

        int[] dp = new int[len];
        Arrays.fill(dp, 1);

        int maxVal = 0;

        for(int i=len-2; i>-1; i--){
            int maxDp = 0;
            for(int j=i+1; j<len; j++){
                if(nums[i] < nums[j]){
                    maxDp = Math.max(maxDp, dp[j]);
                }
            }
            dp[i] = maxDp+1;
            if(maxDp+1 > maxVal) maxVal = maxDp+1;
        }
        return maxVal;
    }
}