[LeetCode- Ch8. 동적계획법] 4. 가장 긴 증가하는 서브시퀀스

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

Longest Increasing Subsequence - LeetCode

 

참고 자료

https://and-some.tistory.com/643

[Ch.10 - DP] 03. 최대 부분 증가수열 [+LIS]

 

---

1. dp[i] : i의 위치에서 가장 긴 증가하는 서브시퀀스

2. i이전의 정수값과 비교해가면서 제일 큰 위치에서 정수값이 더 크면 +1한 값을 넣는다. 

 

class Solution {
    public int lengthOfLIS(int[] arr) {
        //dy[i] : 수열에서 i번째 숫자를 마지막으로 하는 최대 증가 수열의 길이
        int n=arr.length;
        int[] dp = new int[n];
        //[10,9,2,5,3,7,101,18]
        Arrays.fill(dp, 1);
        
        //(i 이전의 최대 증가 수열의 길이)와 (만약 해당 위치의 정수값보다
        //정수값이 더 크면, 자신의 최대 증가 수열의 길이+1)과 비교
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                //1>0 -> dp[1]= Math.max(0, dp[0]+1);
                if(arr[i]>arr[j]) 
                    dp[i]=Math.max(dp[i], dp[j]+1);
            }
        }
        int answer=Integer.MIN_VALUE;
        for(int x: dp) {
            System.out.print(x+" ");
            answer=Math.max(x,answer);
        }
        return answer;
    }
}