You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
54 lines
1.2 KiB
54 lines
1.2 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
int a[101] = {0};
|
|
int f[101] = {0};
|
|
int n;
|
|
//用一层循环获取连续最大子序列和，注意，不是连续递增最大子序列和问题
|
|
int max_subsequence_sum() {
|
|
int this_sum, max_sum, j;
|
|
|
|
this_sum = max_sum = 0;
|
|
for (j = 1; j <= n; j++) {
|
|
this_sum += a[j];
|
|
if (this_sum > max_sum)
|
|
max_sum = this_sum;
|
|
else if (this_sum < 0)
|
|
this_sum = 0;
|
|
else
|
|
cout << "no action" << endl;
|
|
}
|
|
return max_sum;
|
|
}
|
|
|
|
int main() {
|
|
//输入+输出重定向
|
|
freopen("../1281.txt", "r", stdin);
|
|
|
|
//动态规则(记录了最大值的DP表)
|
|
|
|
cin >> n;
|
|
for (int i = 1; i <= n; ++i) {
|
|
cin >> a[i];
|
|
}
|
|
for (int i = 1; i <= n; i++) {
|
|
f[i] = a[i];
|
|
for (int j = 1; j < i; j++) {
|
|
if (a[j] < a[i] && f[j] + a[i] > f[i]) {
|
|
f[i] = f[j] + a[i];
|
|
}
|
|
}
|
|
}
|
|
//输出dp表
|
|
int maxx = INT32_MIN;
|
|
for (int i = 1; i <= n; i++) {
|
|
if (f[i] > maxx) maxx = f[i];
|
|
}
|
|
cout << maxx << endl;
|
|
|
|
//关闭文件
|
|
fclose(stdin);
|
|
return 0;
|
|
}
|