728x90
분석
[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)
12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS Longest Increasing
karla.tistory.com
[14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색)
14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 분석
karla.tistory.com
풀이
"""
N(2≤N≤1,000, 자연수)
8
5 3 7 8 6 2 9 4
"""
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.insert(0,0)
d=[0]*(n+1)
d[1]=1
res=0
for i in range(2,n+1):
max=0
for j in range(i-1, 0, -1):
if arr[j]<arr[i] and d[j]>max:
max=d[j]
d[i]=max+1
if d[i]>res:
res=d[i]
print(res)
728x90