36 lines
814 B
C++
36 lines
814 B
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
|
|
using namespace std;
|
|
|
|
int get_max_sum(const vector<int>& vec) {
|
|
vector<int> max_sums(vec.size());
|
|
max_sums[0] = vec[0];
|
|
for (int i = 1; i < vec.size(); i++) {
|
|
int max_sum = 0;
|
|
for (int j = 0; j < i; j++) {
|
|
if (vec[j] < vec[i]) {
|
|
max_sum = max(max_sum, max_sums[j]);
|
|
}
|
|
}
|
|
max_sums[i] = max_sum + vec[i];
|
|
}
|
|
return *max_element(max_sums.begin(), max_sums.end());
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
int numbers_amount;
|
|
cin >> numbers_amount;
|
|
vector<int> numbers(numbers_amount);
|
|
for (int i = 0; i < numbers_amount; i++) {
|
|
cin >> numbers[i];
|
|
}
|
|
cout << get_max_sum(numbers) << endl;
|
|
|
|
return 0;
|
|
}
|