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

🍋 문제링크

www.acmicpc.net/problem/11055

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 28776 KB

시간 : 188 ms

🍉 Code

import sys
input = sys.stdin.readline

def find_prev(i, arr, dp):
    tmp=[]
    for j in range(i):
        if (arr[j] < arr[i]):
            tmp.append(dp[j])
    if (len(tmp)==0):
        return -1
    return dp.index(max(tmp))

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

dp = [0]*(n+1)
dp[0] = arr[0]
for i in range(1, n):
    if (find_prev(i, arr, dp) != -1):
        dp[i] = dp[find_prev(i, arr, dp)] + arr[i]
    else:
        dp[i] = arr[i]

print(max(dp))

🥝 메모

<배열의 원소 입력받기>

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