오름세

• 오름세를 다른 말로 하면 증가하는 부분수열이고, 구해야 하는 것은 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS) 의 길이이다. 이는 이분탐색을 이용해서 O(nlogn)에 구할 수 있다.

"""Solution code for "BOJ 3745. 오름세".

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

Tags: [Longest increasing sequence]
"""

import bisect


def lis_length(seq):
    arr = [seq[0]]
    for val in seq:
        if val > arr[-1]:
            arr.append(val)
        else:
            arr[bisect.bisect_left(arr, val)] = val
    return len(arr)


def main():
    while True:
        try:
            N = int(input())  # pylint: disable=unused-variable
            nums = [int(x) for x in input().split()]
        except EOFError:
            break
        print(lis_length(nums))


if __name__ == '__main__':
    main()