百练2757:最长上升子序列
发布时间:2020-12-14 03:49:35 所属栏目:大数据 来源:网络整理
导读:描述 一个数的序列 b i ,当 b 1 ?? b 2 ? ... ? b S 的时候,我们称这个序列是上升的。对于给定的一个序列( a 1 ,? a 2 ,...,? a N ),我们可以得到一些上升的子序列( a i 1 ,? a i 2 ,? a i K ),这里1 =? i 1 ?? i 2 ? ... ? i K ?= N。比如,对于序列(1,
描述
1.递归做法,不说了肯定超时。。 1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int a[1010]; 5 int n; 6 int f(int index)//求以a[index]为终点的最长上升子序列的长度 7 { 8 if(index == 1) 9 { 10 return 1; 11 } 12 int maxV = 1; 13 for(int i = 1;i<index;++i) 14 { 15 if(a[i]<a[index]) 16 { 17 maxV = max(maxV,f(i)+1); 18 } 19 } 20 return maxV; 21 } 22 int main() 23 { 24 cin >> n; 25 for(int i = 1;i<= n;++i) 26 { 27 cin >> a[i]; 28 } 29 int maxV = 0; 30 for(int i = 1;i<=n;++i) 31 { 32 maxV = max(maxV,f(i)); 33 } 34 cout << maxV << endl; 35 return 0; 36 } ?2.“人人为我”递推型,状态是n个,算出每个状态的时候需要一个循环,因此总的时间复杂度是O(n^2)的。 #include<iostream> #include<algorithm> using namespace std; int a[1010]; int dp[1010];//dp[i]表示以a[i]为终点的最长上升子序列的长度 int n; int main() { cin >> n; for(int i = 1;i<= n;++i) { cin >> a[i]; dp[i] = 1;//因为一个数字的最长上升子序列就是它自己,所以初始化所有dp为1 } for(int i = 2;i <=n;++i) for(int j = 1;j<i;++j) { if(a[j]<a[i]) { dp[i] = max(dp[i],dp[j]+1); } } cout << *max_element(dp+1,dp+n+1) << endl; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |