該題應使用動歸 ?時間限制: 1 s ?空間限制: 256000 KB ?題目等級 : 黃金 Gold 題解 ?查看運行結果 題目描述?Description

給一個數組a1, a2 ... an，找到最長的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。

輸出長度即可。

輸入描述?Input Description

第一行，一個整數N。

第二行 ，N個整數（N?<?=?5000）

輸出描述?Output Description

輸出K的極大值，即最長不下降子序列的長度

樣例輸入?Sample Input

5

9?3?6?2?7

樣例輸出?Sample Output

3

數據范圍及提示?Data Size & Hint

【樣例解釋】

最長不下降子序列為3,6,7

#include<cstdio> int n,a; int s[1000001],v[1000001]; int main() {scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&s[i]);v[++a]=s[1];for(int i=1; i<=n; i++){if(v[a]<s[i+1])v[++a]=s[i+1];elsefor(int j=1; j<=a; j++)//if(s[i+1]<v[j]){v[j]=s[i+1];break;}}printf("%d",a);return 0; }

?

解釋 例子 1 3 7 9 4 5 6 10 共這些數 若后面的數大于前面的數，那么我們把a[i]存到v[a]數組中，這樣v數組的下標可以代替最長序列長度。 若后面的數大于前面的數，那么我們用一個for循環找到第一個比這個數大的數，替換。同時，我們可以發現a的大小并沒有發生改變。 即開始時最長序列為 1 3 7 9把7 9 改成4 5后繼續進行以上的內容。

　　nlongn做法

#include<cstdio> using namespace std; int n,f[5001],s,x; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x);if(x>f[s]) {f[++s]=x;continue;}int l=0,r=s,k;while(l<=r){int m=l+r>>1;if(x>f[m]) {l=m+1; k=m;}else r=m-1;}if(f[k+1]>x) f[k+1]=x;}printf("%d",s); }

?

轉載于:https://www.cnblogs.com/z360/p/6361758.html

總結

以上是生活随笔為你收集整理的最长严格上升子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。