[백준/12015/파이썬] 가장 긴 증가하는 부분 수열2

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

Problem

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

조건

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

SOL

LIS를 나타내는 방법에는 3가지가 있다.

O(2^n) , O(n^2),O(Nlogn) 

이 3가지 방법은 각각 다른 방식의 접근을 하고있음! 

이번 문제는 O(NlogN)이 걸리는 친구를 사용해야하는 문제이다. 이 알고리즘은 상당히 어려워, 따로 글을 쓰도록 하겠다. (예전에 LIS를 쓴 글에  추가할거임!) 

 

#LIS
#greedy
import sys
input= sys.stdin.readline
def LIS(arr):
    if not arr:
        return 0
    INF=float('inf')
    C = [INF]*(len(arr)+1)
    C[0] = -INF
    C[1] = arr[0]
    tmp_longest=1
    #Find i that matches C[i-1] < n <= C[i]
    def search(lo,hi,n):
        if lo==hi:
            return lo
        elif lo+1==hi:
            return lo if C[lo]>=n else hi
        
        mid = (lo+hi)//2
        if C[mid] ==n:
            return mid
        elif C[mid]<n:
            return search(mid+1,hi,n)
        else:
            return search(lo,mid,n)
    
    for n in arr:
        if C[tmp_longest]<n:
            tmp_longest+=1
            C[tmp_longest] =n
        else:
            next_loc=search(0,tmp_longest,n)
            C[next_loc] =n
    return tmp_longest

N=int(input().rstrip())
seq=list(map(int,input().split()))
print(LIS(seq))