Longest Ordered Subsequence

Longest Ordered Subsequence

这个嘛，我觉得是m[i]=max(m[0~i-1])+1;完了复杂度是O(n^2/2);

书上开了一个辅助数组d[]，就很nice，思想是如果m[i]>d[最后一个],辣么直接添加进来，

如果m[i]<d[最后一个]，就让它替换掉d[]中第一个比它大的，毕竟比它大的在前面，发展显然没有它好

当然也可以dp

代码嘛……

#include <algorithm>
#include <iostream>
using namespace std;
const int MAX = 1000;
int a[MAX],dp[MAX];
int main(){

int n,m=1;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];

for(int i = 0; i < n; i++) {
dp[i] = 1;
for(int j = 0; j < i; j++) {
if(a[j] < a[i] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
for(int i=0;i<n;i++){
m=(dp[i]>m)?dp[i]:m;
}
cout << m << endl;
return 0;
}

原文链接:https://www.cnblogs.com/sos3210/p/12288386.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有