//最长上升子序列
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 10100;
int a[maxn],dp[maxn];
int n,k;
//a[] 保存原始数据
//dp[i] 表示原始数中以i结尾的上升子序列的长度
int res()
{
dp[0] = 1;
int max = 0;
for(int i = 1;i<n;i++)
for(int j = 0;j<i;j++){
if(a[i]>a[j] && dp[i] < (dp[j]+1))
{
dp[i] = dp[j]+1;
}
if(max < dp[i])
max = dp[i];
}
return max;
}
int main()
{
cin>>n;
for(int i = 0;i<n;i++)
cin>>a[i];
cout<<res()<<endl;
return 0;
}
此算法为O(n^2)
for(int i = 1;i<n;i++) for(int j = 0;j<i;j++)//从头开始查找
{ if(a[i]>a[j] && dp[i] < (dp[j]+1)) { dp[i] = dp[j]+1; } if(max < dp[i]) max = dp[i]; }
//a[] 保存原始数据//dp[i] 表示原始数中以i结尾的上升子序列的长度
转载于:https://www.cnblogs.com/plxx/p/3232731.html
相关资源：19nm 4 4 eMCP(SD7DP24F-4G).pdf
