[백준] 11053 가장 긴 증가하는 부분 수열(Python)

1. 생각 정리

• 무조건 다음 숫자가 지금 보다 크다고 해서 수열에 포함시키면 정답을 구하지 못할 수도 있다
• 수열의 시작부터 전체로 확장해나가며 가장 긴 수열의 길이를 찾아보자
• 길이가 4인 [10,20,10,30] 수열이 있으면 [10]이면 1, [10,20]이면 2, [10,20,10]이면 2, [10,20,10,30]이면 3처럼 확장해나가며 정답을 도출해보자

 

2. 코드 구현

N = int(input())
arr = list(map(int, input().split()))
dp = [1]*N

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