[python] 백준 11055 가장 큰 증가 부분 수열

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

11055번: 가장 큰 증가 부분 수열

 

 

문제 해결

전통적인 dp문제

dp[n]을 n을 마지막으로 포함하는 부분 증가 수열중 합이 가장 큰 수를 나타낸다고 하자.

이 때 들어가는 수열중 n 이전 마지막 수를 i라 할 때 dp[n] = max(dp[i]+A[n], dp[n])이 될 것이다.

따라서 이 것을 생각하고 풀면 끝

 

CODE

import sys
input = sys.stdin.readline
n = int(input())
A = [0]+list(map(int, input().split()))
dp = [0 for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j]+A[i])
print(max(dp))

 

유사 문제

https://thought-process-ing.tistory.com/67

[python] 백준 11722 가장 긴 감소하는 부분 수열