1. 문제

---

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

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

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

2. 아이디어

---

• LIS의 길이가 목표

  1. bisect.bisect_left(arr, x) : arr가 정렬되어 있다는 가정하에 x값이 들어갈 위치를 반환, 경계값은 왼쪽으로 포함
  2. arr을 입력받는다.
  3. 만약 result의 마지막 값보다 현재 arr의 요소인 a의 값이 크다면 append
  4. 그게 아니라면 result에서 a가 있어야 할 위치에 a를 저장한다.

• 진행 과정

  [0, 10]
  [0, 10, 20]
  [0, 10, 20, 30]
  [0, 10, 20, 30, 50]

3. 코드

---

mine

import sys
from bisect import bisect_left

input = lambda: sys.stdin.readline()
n = int(input())
arr = list(map(int, input().split()))
result = [0]

for a in arr:
  if result[-1] < a:
    result.append(a)
  else:
    result[bisect_left(result, a)] = a

print(len(result)-1)