카드 구매하기

• 간단한 DP 문제
• DP[i]를 카드 i장을 가장 비싸게 구입하는 가격이라고 하면, 점화식은 아래처럼 나온다
  • $ DP[0] = 0 \\ DP[x] = \max_{0 \leq i < x}{DP[x-i] + P_i} $
• 점화식대로 DP테이블을 채워나가면서 계산하면 총 시간복잡도는 O(n^2)

"""Solution code for "BOJ 11052. 카드 구매하기".

- Problem link: https://www.acmicpc.net/problem/11052
- Solution link: http://www.teferi.net/ps/problems/boj/11052

Tags: [DP]
"""


def main():
    N = int(input())
    P = [int(x) for x in input().split()]

    dp = [0]
    for _ in range(N):
        dp.append(max(dp_i + p_j for dp_i, p_j in zip(reversed(dp), P)))

    print(dp[-1])


if __name__ == '__main__':
    main()