[python/11053]가장 긴 증가하는 부분 수열

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

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

 

이 문제는 최장 증가 부분 수열(LIS : Longest Increasing Subsequence) 문제로 동적 계획법으로 풀 수 있는 문제입니다.

 

코드를 보시려면 더보기를 누르시면 됩니다.

전체 코드

# 백준 11053 가장 긴 증가하는 부분 수열
 
def solve(N, LIS):
    dp = [1] * N
    for i in range(N):
        for j in range(i):
            if LIS[i] > LIS[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
 
if __name__=='__main__':
    N = int(input())
    LIS = list(map(int, input().split()))
    print(solve(N, LIS))