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

1. 문제 📚

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

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

2. 입출력 예 📋

3. 알고리즘 ✅

N이 1000이기 때문에 완탐으로 하면 시간초과가 날 것이다 

앞부분 수열에 따라 뒷부분 수열까지 영향을 주기 때문에 DP로 풀어야 한다! 

dp 를 1로 초기화해준 다음,

현재 index로 이전의 숫자와 차근차근 비교해서 증가하는 수라면 그 이전에 저장된 dp 값 + 1을 하여 dp 를 변경해준다.

또한, 가장 긴 증가하는 부분이기 때문에 max로 해서 가장 큰 값으로 매번 변경해주어야한다

4. 소스 코드 💻

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().strip().split()))
dp = [1 for _ in range(N)]

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

print(max(dp))