LIS (최장 증가 부분 수열)

Longest Increasing Subsequence

수열의 순서는 유지하되 일부 항을 선택하여 만들 수 있는 수열(부분 수열) 중 각 항이 이전 항에 비해 증가하는 부분 수열

LIS 길이 구하기

1. 1번 항 부터

2. DP배열의 가장 큰 수보다 큰 값이 들어오면 DP 배열에 저장

   • Lower Bound : 자신보다 크거나 같으면서 그 중 가장 작은 숫자

3. DP의 Lower Bound가 이번 항 보다 작으면 Lower Bound자리에 이번 항을 넣음

DP배열의 길이는 LIS의 길이와 같다.
DP배열은 오름차순 정렬이 되어있으므로
Lower bound는 Binary Search로 찾을 수 있다.

Arrays.BinarySearch() 는

• 값을 찾으면
  • 그 값의 index를 반환
• 값을 찾지 못하면
  • 음수를 반환하는데,
  • 이 음수는 -(low+1) 이고 low는 인덱스 값이다.

static int findLIS(){
    dp[0] = arr[0];
    int max_idx = 0;
    for(int i=1; i<arr.length; i++) {
        if(dp[max_idx] < arr[i]){
            dp[++max_idx] = arr[i];
        } else {
            int target;
            int tmp = Arrays.binarySearch(dp, 0, max_idx, arr[i]);
            target = tmp < 0 ? (tmp * -1) -1 :tmp;
            dp[target] = arr[i];
        }
    }
    
    return max_idx + 1;
}