백준 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net

%%풀이%%

a는 입력받은 값을 저장하는 배열,

b는

a[i]

n[i]를 구하려면 n[0]부터 n[i-1] 중 n[i]보다 작은 수 중의 최댓값+=1이다.

즉, n[i]의 왼쪽에있는 수를 비교하여 n[i]보다 작은 수를 찾고,

이중 가장 큰 값(가장 길게 이어저온 배열)에 1을 추가하면 된다.

점화식

n[i]=max( n[:i] < n[i] )+1

이후 배열 b의 가장 큰 값을 구하면 된다.

n=int(input())a=list(map(int,input().split()))b=[0 for _ in range(n)]
for i in range(n):    max_a=0 #최댓값    for j in range(i): #a[i]전까지 a[i]보다 작은수 비교
        if a[j]<a[i]:            max_a=max(max_a,b[j])    b[i]=max_a+1
print(max(b))