1. 문제

---

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

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

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

2. 아이디어

---

• mine (원인 불명 실패 - 틀렸습니다❗)

  1. bisect를 사용한 LIS

clone

1. bisect를 사용한 LIS 리스트 : q
2. (들어갈 위치, 값)의 쌍을 넣는 배열 : t
3. 들어갈 위치와 인덱스를 비교하여 ans에 추가 -> [50, 30, 20, 10]

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 L

n = int(input())
arr = list(map(int, input().split()))
result = get_lis_improved(arr)
print(len(result))
for res in result:
  print(res, end = ' ')

clone

import sys
from bisect import bisect_left
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))

q=[arr[0]]
t=[] # (들어갈 위치, 값)의 쌍을 넣는 배열
# 여기는 이전 문제들과 비슷하다.
#  다만 t라는 새로운 배열에 갱신되는 배열 요소의 위치, 요소 값에 대한 정보도 추가하는게 다르다
for x in arr:
    if q[-1]<x:
        q.append(x)
        t.append((len(q)-1,x))
    else:
        idx=bisect_left(q,x)
        q[idx]=x
        t.append((idx,x))

# 최종 배열의 길이를 구했으면 마지막 위치부터 가장 큰 요소를 넣는다 (실제 요소)       
last_idx=len(q)-1

# 덮어씌워진 요소가 아니라 기존 요소를 넣어준다 
ans=[]
for i in range(n-1,-1,-1):
    if t[i][0]==last_idx:
        ans.append(t[i][1])
        last_idx-=1

print(len(q))
# *을 붙이면 자동으로 리스트 요소를 공백으로 구분해 반환해준다
print(*reversed(ans))

출처 : https://haerang94.tistory.com/131