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

문제

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

풀이

i번째 수에서의 증가하는 수열의 길이를 구할때, 1 ~ i-1번째 까지의 수들과 비교를 하며 수열의 길이를 최신화 해준다. 단, i번째 수보다 작다고 최신화 하는 것이 아닌 i번째 수의 길이와도 비교해서 최신화 해줘야 한다.

max(dp[j]+1, dp[i])

코드

from sys import stdin

input = stdin.readline

n = int(input())

array = list(map(int,input().split()))

dp = [1 for i in range(n)]

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

print(max(dp))

비슷한 문제

11055번 : 가장 큰 증가 부분 수열 / 풀이
11054번 : 가장 긴 바이토닉 부분 수열 / 풀이
12015번 : 가장 긴 증가하는 부분 수열 2 / 풀이