51nod 1134 最長遞增子序列

2022-09-23 01:22:01 字數 1219 閱讀 7988

給出長度為n的陣列,找出這個陣列的最長遞增子序列。(遞增子序列是指,子序列的元素是遞增的)

例如:5 1 6 8 2 4 5 10,最長遞增子序列是1 2 4 5 10。

input

第1行:1個數n,n為序列的長度(2 <= n <= 50000)

第2 - n + 1行:每行1個數,對應序列的元素(-10^9 <= s[i] <= 10^9)

output

輸出最長遞增子序列的長度。

input示例

851

6824

510

output示例

5

//第一種做法,放入一個數然後更新

#include #include #include using namespace std;

long long a[100000],b[100000];

int main()

}} cout……額 ……┭┮﹏┭┮……等我不這麼菜了,再改

建立一個輔助陣列c[n],c[i]儲存的是子序列長度為i的序列最後一值即

子序列長度為i有多個,但是要求最後一個值最小,

比如 1, 4,7,3,8,2,1

1,41,3

1,21,1

從前往後遍歷陣列a[n],處理a[i-1]時,觀察c陣列,每個a陣列中的值和

c陣列中的值進行比較,找到合適的位置插入(若插入到c陣列的末尾,那麼

所求最長上升子序列長度+1,恩,,你應該隱約感受到了什麼了吧,不錯呢c陣列的

長度就是最後我們所要求滴,撤回來),否則就替換掉c陣列原來位置上的值

這有助於我們通過a陣列計算b陣列(b[i]中儲存的是以a[i]為最後一個元素的

最長單調遞增子序列) 若a[i]

由於c陣列下標代表子序列長度,c陣列中的值也是按遞增序列排序,所以很符合二分

#include using namespace std;

int find(int *a,int len,int n)

}void init(int *a,int n)

int main()

for(maxn=i=0;i//遍歷一遍找到最大值

if(b[i]>maxn)

maxn=b[i];

cout<} return 0;

}

51nod 1134最長遞增子序列

給出長度為n的陣列,找出這個陣列的最長遞增子序列。 遞增子序列是指,子序列的元素是遞增的 例如 5 1 6 8 2 4 5 10,最長遞增子...

51nod 1218 最長遞增子序列 思維題

給出一個序列,求哪些元素可能在某條最長上升子序列中,哪些元素一定在所有最長上升子序列中。 yjy大嫂教導我們,如果以一個元素結尾的lis長度...

51nod 1522 上下序列

現在有1到n的整數,每一種有兩個。要求把他們排在一排,排成一個2 n長度的序列,排列的要求是從左到右看,先是不降,然後是不升。 特別的,也可...