题解 | #最大上升子序列和#
最大上升子序列和
https://www.nowcoder.com/practice/dcb97b18715141599b64dbdb8cdea3bd
#include <bits/stdc++.h>
using namespace std;
int dp[1001];
int main() {
int N;
while (scanf("%d", &N) != EOF) {
int arr[N];
for (int i = 0; i < N; ++i) {
scanf("%d", &arr[i]);
}
dp[0] = arr[0];
int answer = 0;
for (int i = 1; i < N; ++i) {
dp[i] = arr[i];
for (int j = 0; j < i; ++j) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], dp[j] + arr[i]);
}
}
answer = max(answer, dp[i]); //dp数组的最大值
}
printf("%d\n", answer);
}
return 0;
}
投递金山WPS等公司10个岗位 >
