백준 11055번 C++

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAX = 1001;

int n;

int arr[MAX];

int minsum[MAX];

int calminsum() {

minsum[1] = arr[1];

for (int i = 2; i <= n; i++) {

int maxs = 0, index = 0;

for (int k = i - 1; k >= 1; k--) {

if (arr[k] < arr[i]) {

if (maxs < minsum[k]) {

maxs = minsum[k];

index = k;

}

}

}

minsum[i] = arr[i] + minsum[index];

}

int result = minsum[1];

for (int i = 2; i <= n; i++) {

result = max(result, minsum[i]);

}

return result;

}

int main(void) {

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> arr[i];

}

cout << calminsum();

}