1. 문제

---

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

출처 : https://www.acmicpc.net/problem/12738

2. 아이디어

---

• mine

  1. 반도체 설계와 같은 원리

3. 코드

---

mine

import sys
from bisect import bisect_left
input = sys.stdin.readline

def get_lis_improved(sequence):
  L = [sequence[0]]
  for i in range(1, len(sequence)):
    if L[-1] < sequence[i]:
      L.append(sequence[i])
    else:
      lower_bound = bisect_left(L, sequence[i])
      L[lower_bound] = sequence[i]
  # print(L)
  return len(L)

n = int(input())
arr = list(map(int, input().split()))
print(get_lis_improved(arr))