[백준 알고리즘] 11053번 가장 긴 증가하는 부분 수열. 파이썬(python)

n=int(input())
a=list(map(int, input().split()))
dp=[1]*n

for i in range(n):
    for j in range(i):
        if a[i]>a[j]: # 현재i가 이전j보다 크다면
            print('i,j',i,j)
            print('전',dp)
            dp[i]=max(dp[i],dp[j]+1)
            print('후',dp)
            print()

print(max(dp))

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

수열 = [10, 20, 10, 30, 20, 50]

i,j 3 0

현재 값: 30, 전 값: 10

현재 값이 더 크므로 dp[j]+1 선택
전 [1, 2, 1, 1, 1, 1]
후 [1, 2, 1, 2, 1, 1]

수열 = [10, 20, 10, 30, 20, 50]

i,j 3 1

현재 값: 30, 전 값: 20

현재 값이 더 크므로 dp[j]+1 선택

전 [1, 2, 1, 2, 1, 1]
후 [1, 2, 1, 3, 1, 1]

수열 = [10, 20, 10, 30, 20, 50]

현재 값이 더 크므로 dp[i] 선택

=> 앞에서 이미 10,20,30으로 3이 됐는데 여기서 10,30을 선택하면(dp[j]+1) 2가 되므로 d[i]가 최대가 된다.
i,j 3 2
전 [1, 2, 1, 3, 1, 1]
후 [1, 2, 1, 3, 1, 1]

 

결론

현재 값을 선택했다는 가정 하에(dp를 1로 초기화한 이유)

전의 값들에서 현재 값보다 작은 것이 몇개인지 카운팅 한다.

import sys
input=sys.stdin.readline

n=int(input())
a=list(map(int, input().split()))
dp=[1]*n

for i in range(n):
    for j in range(i):
        if a[i]>a[j]: # 현재i가 이전j보다 크다면
            dp[i]=max(dp[i],dp[j]+1)
print(max(dp))