[백준] 11052 - 카드 구매하기 (파이썬)

import sys

n = int(sys.stdin.readline())
array = [0]
array += list(map(int,sys.stdin.readline().split()))
dp = [0,array[1]]
k = 1

if n==1:
    print(array[1])
else:
    for i in range(2,n+1):
        maxim = array[i]
        for j in range(i//2):
            maxim = max(maxim,dp[k+j]+dp[i-k-j])
        dp.append(maxim)
        

print(dp[n])