백준 | 가장 큰 증가하는 부분 수열

가장 큰 증가하는 부분 수열

import sys


n = int(sys.stdin.readline().strip())
ary = list(map(int, sys.stdin.readline().strip().split()))

# dp[i]: i번째까지의 증가하는 부분 수열 중 합이 가장 큰 것
dp = ary.copy()
for i in range(1, n):
    temp = []

    for j in range(i):
        # ary[j]에서 ary[i]로 이어지는 수열이 증가하는 부분 수열인 경우
        if ary[i] > ary[j]:
            # dp[j]에 현재 수열의 값 ary[i]를 더한 값이 dp[i]의 후보가 될 수 있다.
            temp.append(ary[i] + dp[j])
    
    # max([])는 ValueError가 발생하므로, 분기 처리가 필요하다.
    if temp:
        dp[i] = max(temp)

print(max(dp))

위의 코드를 리팩토링하면 다음과 같다.

import sys


n = int(sys.stdin.readline().strip())
ary = list(map(int, sys.stdin.readline().strip().split()))

dp = ary.copy()

for i in range(1, n):
    for j in range(i):
        if ary[i] > ary[j]:
            dp[i] = max(dp[i], dp[j] + ary[i])

print(max(dp))