[Python] 백준 11052번 - 카드 구매하기

N = int(input())
prices = [0] + list(map(int, input().split()))
max_prices = [0 for _ in range(N+1)]
for i in range(1, N+1):
    # 한 줄 씩
    index = (i+1) // 2
    maxForI = prices[i]
    for j in range(index, i):
        if (max_prices[j] + max_prices[i-j]) > maxForI:
            maxForI = (max_prices[j] + max_prices[i-j])
    max_prices[i] = maxForI
print(max_prices[N])