백준 11053: 가장 긴 증가하는 부분 수열 해설- python

✏️ 문제

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

11053

✏️ 풀이

LIS(Longest Increasing Subsequence)라는 유명한 DP문제이다.만약 A={6, 2, 5, 1, 7, 4, 8, 3} 가 있을때 LIS는 {2, 5, 7, 8}이 된다. 증가하는 수열은 {2, 5}, {2, 7} 등 많지만 그 중 가장 긴 것이 LIS가 된다.

 

- dp[i]를 전부 1로 초기화했다. LIS의 길이는 기본적으로 1은 될 것이기 때문.

- 현재위치(i) 보다 이전에 위치한 원소(j)의 크기가 더 작은지를 확인. LIS를 만들기 위함.

- 작은게 맞다면 현재위치로부터 이전숫자로까지의 dp중 max를 구하고 +1해준다.

 

n=int(input())
dp=[1]*n
A=list(map(int,input().split()))


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

print(max(dp))