[DP]LIS

Longest Increasing Subsequence(최장 증가 부분배열)

public int LIS(int[] arr) {
    int res=0;
    int[] dp=new int[60000];
    dp[0]=1;
    for(int i=1; i<arr.length; i++){
        int val=0;
        for(int j=0; j<i; j++){
            if(arr[j]<arr[i]){
                if(val<dp[j]) val=dp[j];
            }
        }
        dp[i]=val+1;
    }
    for(int el : dp){
        if(el>res) res=el;
    }
    return res;
  }

• dp 배열을 선언하고 첫번째 요소를 1로 초기화
• 차례로 순차접근하여 해당 인덱스 이전의 값을 다시 for문으로 돌면서 해당 인덱스의 값보다 작은 값을 가지는 값의 dp 값 중 가장 큰 값을 구하고 1을 더한 값을 해당 dp에 할당한다.
• 마지막으로 처음부터 순차접근하여 최대값을 구한다.