[백준] 11055: 가장 큰 증가 부분 수열 (Python)

문제📖

풀이🙏

• dp를 이용하여 현재 인덱스보다 이전에 작은 값을 만나면 이전 작은 값까지의 증가 부분 수열의 합 더하기 현재 위치의 값으로 dp를 갱신한다.
• 이 때 주의해야할 부분은 현재 인덱스보다 이전에 작은 값이 없는 경우를 고려하여 data의 내용을 dp에 먼저 복사해 놓는다.

코드💻

from copy import deepcopy
n = int(input())
data = list(map(int, input().split()))
dp = deepcopy(data)

for i in range(1,n):
    for j in range(i):
        # 현재 인덱스보다 이전에 작은 값을 만나면
        # 이전 작은 값까지의 증가 합 더하기 현재 위치 값이 가장 큰 값을 구한다.
        if data[j] < data[i]:
            dp[i] = max(dp[j]+data[i], dp[i])
print(max(dp))