[백준11055] / 가장 큰 증가하는 부분 수열 - DP

 

백준11055

 

푼 날짜 : 2024.09.21

푼 문제 : [11055] / 가장 큰 증가하는 부분 수열

사용한 언어 : python

알고리즘 : DP

 

 

점화식:

dp[i] = max(dp[i], dp[j]+lst[i]) (if lst[j] < lst[i])

 

여기서 뽀인트🌟 는 i번째 반복이 끝날 때 현재 dp[i]와 lst[i]를 비교해서 큰 값을 넣어주는 것!

안그러면 lst[i]는 0보다 큰 수 인데 dp[i]에는 0이 들어가 있게 된다.

 

이렇게 되면 다음 계산에 영향을 준다!!

 

 

 

코드 :

import sys

N = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(N)]
dp[0] = lst[0]

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

print(max(dp))

 

 

오늘도 1솔 성공 ^____^