[백준 / 11053] 가장 긴 증가하는 부분 수열 - Python

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

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

 

<풀이>

현재 수가 이 전들의 수와 비교하면서, 만약 그 수보다 크다면 해당 수의 길이에 +1을 하거나, 지금 수가 더 크면 현재 값을 유지하면 된다.

 

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

 

 

dp에는 해당 Index의 부분수열의 값이 저장되어 있다.

 

 

<전체 코드>

N = int(input())
arr = list(map(int, input().split()))

dp = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))