Dynamic Programming - Longest Increasing Subsequence (LIS)

Longest Increasing Subsequence (LIS)

• 같은 숫자는 허용 X
  ⇒ 허용하는 경우 : 예를 들어 3이 여러개 있을 때 각각의 3을 3.1, 3.2, 3.3 … 으로 바꾸면
  여전히 알고리즘 적용 가능.
• 불연속이어도 됨.

O(n²) 알고리즘

입력 값이 Arr(i) 에 주어진다고 하였을 때
LIS(i) 는 Arr(i)를 포함하여 (i) 까지 오면서 가장 큰 LIS 이다.

⇒ 즉, Arr(0) ~ Arr(i-1) 들중 Arr(i)보다 작은 값들(Increasing 해야하므로) 중에서
LIS가 가장 큰값 + 1(Arr(i)를 포함) = LIS(i)

---

DP Optimization - O(nlogn)

• DP 결과의 데이터를 분석하여 최적화 하기.
• 불필요한 계산이나 중복되는 계산을 지우자.

---

1. 같은 LIS간의 데이터 분석과 최적화

LIS(i) = k, LIS(j) = k 처럼 DP 값이 같은 경우가 존재한다. (i < j)
이때 Arr(i) 와 Arr(j)를 비교하자.

1. Arr(i) > Arr(j) 는 가능하다.
2. Arr(i) = Arr(j) 는 가능하다.
3. Arr(i) < Arr(j) 는 불가능하다.
왜냐하면 LIS(j) ≥ LIS(i) + 1 이기 때문이다.

따라서 LIS = k 가 되는 Arr(?)의 값들은 전체적으로 모아놓으면 우하향 곡선을 그린다.

이때 새로 들어오는 입력 Arr(x)에 대하여 LIS(x)를 계산해야 한다고 하자.

이제 LIS 값들이 같은 애들에 한해서는
1. LIS = k 우하향 곡선의 가장 마지막이자
2. 가장 낮으며
3. x와 가장 가까운 t의
Arr(t)만을 가지고 Arr(x)와 비교하면 된다.
⇒ 가장 낮은 Arr(t)가 LIS(t)를 만들어내는 최소 조건이기 때문이다.
따라서 LIS(t) 와 같은 LIS 를 가지는 Arr(i) 와 Arr(j)는 Arr(t)보다 큰 값이므로 비교대상에서 제외된다.

1. 만약 Arr(t) < Arr(x) 라면
무조건 LIS(t) < LIS(x) 이다.
2. Arr(t) > Arr(x) 라면
무조건 LIS(t) > LIS(x) 이다.

이를 통해 같은 값들에 한해서는 여러번 비교할 것을 한 번 비교하는것으로 최적화 할 수 있다.

---

2. 최적화된 LIS간의 데이터 분석

이렇게 모든 서로다른 가능한 LIS 값들의 최적 Arr(%)(마지막 입력값)들을 구했고
그 최적에 대한 LIS(t) 와 LIS(k)가 있다고 하자.

LIS(t) < LIS(k) 일 때
1. Arr(t) < Arr(k) 는 가능하다.
2. Arr(t) ≥ Arr(k) 는 불가능하다.

LIS(t) = 3, LIS(k) = 4 라고 해보자.
4를 만들기 위해선 3을 만들어내는 최소조건보다 입력값이 커야한다.
Arr(t) 와 Arr(k) 가 각각 3과 4를 만들어내는 최소조건이므로 즉, Arr(t) < Arr(k) 이다.
따라서 Arr(t) ≥ Arr(k) 는 불가능하다.

그러므로 LIS 로 정렬 하였을 때 Arr(%)들은 상향하는 지그재그를 그린다.
(t < k 나 t > k 인것은 상관이 없기 때문)

---

3. 알고리즘 개선

따라서 LIS 순서로 다음의 배열 O을 정의 할 수 있다.
* 인덱스 : DP 값 LIS(%) = Li
* 배열 값 : DP 를 가진 마지막 입력 값 Arr(%)

이제 새로 들어오는 입력 Arr(x)에 대하여 O(L1) < Arr(x) < O(L2) 라면
이제 Arr(x)가 LIS 값 L2를 가지는 가장 낮은 입력값이므로
O(L2) = Arr(x) 으로 갱신하고 LIS(x) = L2 으로 계산하면 된다.

[최장 증가 수열] LIS(Longest Increasing Subsequence)

12738번: 가장 긴 증가하는 부분 수열 3

C# 풀이

public static int LowerBound(List<long> arr, long value)
{
    int left = 0;
    int right = arr.Count;

    while(left < right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] < value) left = mid + 1;

        else right = mid;
    }

    return right;
}

public static void Main()
{
    var n = int.Parse(Console.ReadLine());
    var arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

    var lis = new List<long>();
    lis.Add(-1);

    for(int i=0; i<n; i++)
    {
        if (arr[i] > lis[lis.Count-1])
        {
            lis.Add(arr[i]);
        }
        else
        {
            int index = LowerBound(lis, arr[i]); // 이진 탐색으로 하한선 찾기
            
            lis[index] = arr[i];
        }
    }
    
    Console.WriteLine(lis.Count - 1);
}