최장 증가 부분 수열

원소가 n 개인 배열의 일부 원소를 골라내어 만든 부분 수열 중에서, 각 원소가 이전 원소보다 크다는 조건을 만족하면서, 그 길이가 최대인 부분 수열

• $O(n^2)$ 풀이

  • 간단한 동적 계획법 이용

  • 위치 k 에서 끝나는 LIS 의 ‘길이’ 를 length(k) 라고 할 때

    • 0 ≤ k ≤ (n - 1) 을 만족하는 모든 k 에 대해 length(k) 값을 차례대로 구하면서, 최종적으로 전체 수열에서의 LIS 를 구함

  • 예시

    for (int k = 0; k < n; k++) {
    	length[k] = 1;
    	for (int i = 0; i < k; i++)
    		if (array[i] < array[k])
    			length[k] = max(length[k], length[i] + 1);
    }
    
    int lenLIS = 0;
    for (int i = 0; i < n; i++)
    	if (length[i] > lenLIS)
    		lenLIS = length[i];
    

  • 단점

    • 수열의 크기가 100,000 이상이 되는 경우, 최악의 경우 10,000,000,000 번의 연산을 수행해야 하므로 주로 시간 초과

• $O(n\;log\;n)$ 풀이

  • 이분 탐색을 활용한 동적 계획법 이용

    • 전체 수열을 순차적으로 확인하면서 LIS 를 유지할 수 있는 요소의 인덱스와 값을 각각 따로 저장
      • 주로 {요소의 인덱스, 값} 의 pair 배열을 선언하여 저장
    • 순차적으로 확인하면서,
      • LIS 를 유지할 수 있는 요소라면 {LIS 를 유지할 수 **있는** 해당 요소의 인덱스, 해당 요소의 값} 을 pair 배열의 뒤에 삽입
      • LIS 를 유지할 수 없는 요소라면, 해당 요소의 값보다 ‘크거나 같은’ 요소가 pair 배열에서 가장 처음 나타나는 위치를 lower_bound 로 이분 탐색
      • 탐색한 pair 배열의 요소의 값을 {LIS 를 유지할 수 **없는** 해당 인덱스, 해당 요소의 값} 의 형태로 수정
      • 전체 수열을 모두 탐색하면 LIS 를 유지할 수 **있는** 요소의 인덱스의 가장 큰 값을 통하여 LIS 의 길이 를 구할 수 있음
    • LIS 원소들 각각의 값은 stack 을 이용하여 역추적해야 알 수 있음
      • 전체 수열의 마지막 요소부터 거꾸로 탐색을 진행
        • 전체 수열의 요소마다 LIS 를 유지할 수 **있는** 요소 였는지, LIS 를 유지할 수 **없는** 요소 였는지 확인 후 pair 배열에 인덱스를 저장하였으며
        • LIS 의 길이 를 알아내었으므로, LIS 의 인덱스 와 전체 수열의 인덱스 를 비교할 수 있게 되었으므로
      • 전체 수열의 해당 요소가 LIS 를 유지할 수 **있는** 요소 라면 stack 에 해당 요소의 값 을 push 해주면 됨

  • 예시

    /* LIS 길이 구하기 */
    int getLenLIS(void) {
      cache[0] = seq[0];
      arrLIS.push_back({0, seq[0]});
    
      int idxLIS = 0;
      for (int i = 1; i < lenSeq; i++) {
        if (cache[idxLIS] < seq[i]) {
          idxLIS++;
          cache[idxLIS] = seq[i];
          arrLIS.push_back({idxLIS, seq[i]});
        } else {
          int idxLowerBound = lower_bound(cache, cache + idxLIS, seq[i]) - cache;
          cache[idxLowerBound] = seq[i];
          arrLIS.push_back({idxLowerBound, seq[i]});
        }
      }
    
      return idxLIS + 1;
    }
    

    int lenLIS = getLenLIS();
    
    /* 구해낸 LIS 길이와 stack을 통해 전체 수열에서 LIS 값 추출 */
    stack<int> s;
    int idxTrace = lenLIS - 1;
    for (int i = lenSeq - 1; i >= 0; i--) {
      if (arrLIS[i].first == idxTrace) {
        s.push(arrLIS[i].second);
        idxTrace--;
      }
    }
    while (!s.empty()) {
      cout << s.top() << " ";
      s.pop();
    }
    cout << "\\n";