출처 - https://www.acmicpc.net/problem/11052

[ 코드 ]

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
   int N;
   cin >> N;
   int* pi = new int[N + 1];
   for (int i = 1; i < N + 1; ++i) {
      cin >> pi[i];
   }
   int* p = new int[N + 1];
    p[0]=0;
   for (int i = 1; i < N + 1; ++i) {
        p[i] = pi[i];
      for (int j = 1; j < i + 1; ++j) {
         p[i] = max(p[i], p[i - j] + pi[j]);
      }
   }
   cout << p[N] << endl;
   return 0;
}