[DP] 백준 11055번 “가장 큰 증가 부분 수열” Python 풀이

문제 링크

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

풀이

• 증가 부분 수열이란?
  • 각 원소가 이전 원소보다 크다는 조건을 만족하는 부분 수열을 의미합니다.
• 따라서, 아래 DP 테이블과 점화식을 사용해 해결할 수 있습니다.
  • dp[i] : i번째 수를 마지막 원소로 가지는 부분 수열의 합
  • 0 ~ i-1번째 원소들을 순서대로 탐색하며, [i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + i번째 원소의 값]을 dp[i]로 기록합니다.

코드

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split(" ")))

# dp 테이블 초기화
dp = [x for x in arr]

for i in range(n):
    for j in range(i):
        # i번째 수보다 작은 수에 대해서
        if (arr[j] < arr[i]):
            # dp 테이블의 i번째 값과 [dp 테이블의 j번째 값 + i번째 원소의 값]을 비교한 뒤,
            # 최댓값을 dp[i]로 기록
            dp[i] = max(dp[i], dp[j] + arr[i])

print(max(dp))