[백준/파이썬] 11053 가장 긴 증가하는 부분 수열

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

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

d[0]은 수열 A의 첫 번째 원소보다 작은 수를 카운트한다.

ex)
i=2
if 10<a[2], if 20<a[2]

[1, 2, 1, 1, 1, 1][1, 2, 1, 2, 1, 1][1, 2, 1, 3, 1, 1][1, 2, 1, 3, 1, 1]
[1, 2, 1, 3, 2, 1][1, 2, 1, 3, 2, 1][1, 2, 1, 3, 2, 2][1, 2, 1, 3, 2, 3]
[1, 2, 1, 3, 2, 3][1, 2, 1, 3, 2, 4][1, 2, 1, 3, 2, 4]

소스코드

n=int(input())
a=list(map(int, input().split()))

d=[1]*n
for i in range(1,n):
  for j in range(i):
    if a[j]<a[i]:
      d[i]=max(d[i],d[j]+1)

print(max(d))