파이썬 가장 긴 증가하는 부분 수열(백준 BOJ 11053)

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

📝 풀어보기

dp에 첫번째 인덱스부터 길이의 최댓값을 저장해나간다.

첫번째 숫자부터 순회하면서 비교하는 값이 이전 값들보다 크고, 저장한 길이의 값이 비교하는 값보다 작을 경우에 최댓값을 갱신한다.

for i 를 돌면서 dp[i]에 1씩 누적하고 dp의 최대값을 구한다.

n = int(input()) # 6
a = list(map(int, input().split())) # 10 20 10 30 20 50
dp = [0 for i in range(n)] # [0, 0, 0, 0, 0, 0]
for i in range(n): # 6
    for j in range(i):
        print(i, j)
        # i = 122333444455555
        # j = 001012012301234
        # 비교하는 a[i] 값이 순회하는 이전값들 보다 크고, 
        # 저장한 길이값이 비교값보다 작을 경우 
        if a[i] > a[j] and dp[i] < dp[j]: 
            dp[i] = dp[j] # 최댓값 저장
    dp[i] += 1 # 1씩 누적
print(max(dp))