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

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

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

 

dp[i] = i 를 마지막 원소로 가지는 증가하는 부분 수열의 길이

A[i] > A[j] (단, j = 0,1,2, ..., i-1) 일 경우 dp[j] + 1 중 가장 큰 값을 dp[i] 로 설정한다. 

dp 의 최댓값을 반환하면 된다.

 

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
dp = [0] * N
answer = 0

for i in range(N):
    val = 0
    
    for j in range(i):
        if A[i] > A[j]:
            val = max(val, dp[j])
    
    dp[i] = val + 1
    answer = max(answer, dp[i])

print(answer)