나연 정렬

• 오름차순으로 정렬한다는 말은, 엄밀하게는 비내림차순으로 정렬한다는 말로 이해하면 된다.
• 같은 스택에 들어간 원소간의 순서 관계는 그대로 역순으로 빠지게 되고 중간에 바뀔수 없다. 그러므로 각각의 스택에 들어있는 원소들은 비내림차순으로 정렬되어 있어야 한다 (top에 가장 작은 원소가 들어있도록..). 이렇게 하려면 각 스택에 원소를 추가할때에는 비오름차순으로 추가해야 한다는 말과 같다.
• 결국 정렬을 하기위해서 원소들을 적절한 스택에 넣는 것은, 전체 수열을 몇개의 비오름차순 부분수열들로 나누고, 각각의 부분수열에 대응하는 스택에 모든 원소를 넣는 것과 같다. 스택의 최소 개수를 구하는 것은 수열을 최소 개수의 비오름차순 부분수열로 나누는 것과 같다. 이 개수를 구하는 것은 그냥 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence; LIS)의 길이를 구하는 것과 동일하다. 시간복잡도는 O(nlogn).

"""Solution code for "BOJ 32873. 나연 정렬".

- Problem link: https://www.acmicpc.net/problem/32873
- Solution link: http://www.teferi.net/ps/problems/boj/32873

Tags: [lis]
"""

import sys
from teflib import seqtask


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    A = [int(x) for x in sys.stdin.readline().split()]

    print(seqtask.length_of_longest_increasing_subsequence(A))


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.length_of_longest_increasing_subsequence