[백준] 11053번(python 파이썬)

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

 

수열중 가장 긴 증가하는 부분 수열을 구하는 문제

dp[i] = (a[i] > a[0:i-1]보다 작은 값들 중) max( dp[0 : i-1] ) + 1

n = int(input())
a = list(map(int, input().split()))
dp = [0] * n

def longIncSequence():
    dp[0] = 1
    for i in range(1, n):
        max_value = 0
        for j in range(i):
            if a[i] > a[j]:
                max_value = max(max_value, dp[j])
        dp[i] = max_value + 1

longIncSequence()
print(max(dp))