最大上升子序列和
最大上升子序列和
https://www.nowcoder.com/practice/dcb97b18715141599b64dbdb8cdea3bd?tpId=40&tqId=21409&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking
/*
状态转移方程
sum[i] = max{1, sum[j] + 1} i < j and A[i] > A[j]
边界
sum[i] = A[i] (i = 1, 2, ... n)
*/
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1000;
int A[N], sum[N];
int main()
{
int n;
while (~scanf("%d", &n))
{
for (int i = 0; i < n; i++)
{
scanf("%d", &A[i]);
}
int ans = 0;
for (int i = 0; i < n; i++)
{
sum[i] = A[i];
for(int j = 0; j <= i; j++){
if(A[j] < A[i]){
sum[i] = max(sum[i], sum[j] + A[i]);
}
}
ans = max(ans, sum[i]);
}
printf("%d\n", ans);
}
return 0;
}计算机历年考研复试上机题 文章被收录于专栏
计算机历年考研复试上机题目题解
查看12道真题和解析