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

문제

링크

풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [0] * n

for i in range(n) :
    # 이전 원소와 비교
    for j in range(i-1, -1, -1) :
        # 이전 원소보다 클 때
        if arr[i] > arr[j] :
            # 현재 합 값과 j번째 합 값 + 현재 원소 값 중 큰 걸로
            dp[i] = max(dp[i], dp[j] + arr[i])
    # 위에서 계산되지 않았을 경우 현재 원소값을 받아온다.
    # 계산되지 않은 경우는 수열의 이전 값들 중에서 현재 원소값보다 작은 수가 없을 때
    if dp[i] == 0 :
        dp[i] = arr[i]
print(max(dp))

반례

• https://www.acmicpc.net/board/view/81905
• https://www.acmicpc.net/board/view/87941