알고리즘 - Python / 백준 - 11053번 : 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

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

 

---

풀이

• 주어진 수열중 가장 길게 증가하는 수열을 찾는 문제이다.
• 주어지는 수열의 크기가 1000이 최대이기 때문에 전체를 순회해도 된다고 생각하고 문제를 풀었다.
• 각 dp 배열에 가장 긴 부분수열의 길이를 저장하고 이후 전체를 확인하며 업데이트 한다.
• dp 배열에서 가장 큰 수가 가장 긴 증가하는 부분수열의 길이 이므로 출력한다.

 

import sys
n = int(sys.stdin.readline())
stack = list(map(int, sys.stdin.readline().split(" ")))
dp = [1] * n
for i in range(1,len(stack)):
    sub_stack = [0]
    for t in range(i,-1,-1):
        if stack[i] > stack[t]:
            sub_stack.append(dp[t])
    dp[i] = (max(sub_stack) + 1)
print(max(dp))

---