[DP] 백준 11053번: 가장 긴 증가하는 부분 수열(BOJ, Python, 파이썬)

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

11053번: 가장 긴 증가하는 부분 수열

 

문제

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

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

 

✔ 풀이

import sys
n=int(sys.stdin.readline())

s=list(map(int,sys.stdin.readline().split()))
result=[1]*n

for i in range(1,n):
    for j in range(i):
        if s[j] < s[i]:
            result[i]=max(result[i],result[j]+1)


print(max(result))