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

---

문제 파악

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

가장 긴 증가하는 부분 수열 이라 함은

수열 A = {10, 20, 10, 30, 20, 50} 인 경우에
{10, 20, 30, 50} 가 가장 긴 증가하는 부분 수열이다.

---

수열의 크기 N이 백만 이하이기 때문에
완전탐색은 불가능 해 보인다.

핵심 아이디어

tails 배열

LIS를 직접 저장하지 않고,
LIS의 “길이만” 관리하는 tails 라는 배열을 하나 만든다.

tails[i] =
→ “길이가 i+1인 증가 수열이 존재할 때, 그 수열의 ‘가능한 최소 마지막 값’”

핵심은 값이 아니라 길이가 중요하다는 점.

tails 자체가 실제 LIS는 아니지만,
tails의 길이 = LIS 길이는 항상 성립한다.

---

lower_bound 함수

새로운 값 x를 tails에 넣을 때,

• x보다 크거나 같은 값이 처음 등장하는 위치를 찾아서
  그 자리를 x로 교체한다.
• 만약 tails 안에 x보다 크거나 같은 값이 없다면
  tails 뒤에 그대로 붙인다.

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

tails = []  # tails[i] = 길이가 i+1인 LIS의 '가능한 최소 마지막 값'

	# array에서 target값 보다 크거나 같은 값이 나오는 첫 인덱스 리턴
    def lower_bound(array, target):
    left = 0
    right = len(array) - 1
    res = len(array)  # 기본값: target 보다 큰 값이 없다면 맨 뒤에 들어간다.

    while left <= right:
        mid = (left + right) // 2

        if array[mid] >= target:
            res = mid
            right = mid - 1
        else:
            left = mid + 1

    return res


for x in arr:
    # tails라는 배열 안에서 x보다 크거나 같은 값이 처음 나오는 위치
    idx = lower_bound(tails, x)

	# x보다 크거나 같은 값이 tails 안에 없다면, 맨 뒤에 붙인다.
	if not tails or x > tails[-1]:
        tails.append(x)
    else:
        # x값이 taiis 배열에서 최댓값이 아니라면, 그 위치 값을 x로 '갈아끼운다'
        tails[idx] = x

print(len(tails))