?

目錄

?

Q1：簡單遍歷

Q2：變式（加大數據量）

---

Q1：簡單遍歷

Dp問題	狀態表示 f(i,j)	集合	所有以第i個數結尾的上升子序列集合
			-
		f(i,j)的值存的是什么	序列長度最大值max
			-
	狀態計算 （其實質是集合的劃分）	劃分	f[ i ] = max(f[ i ] , f [ j ]+1), j < i ,a[ j ]<a[ i ] 以上面的條件作為選或不選聚類形成劃分依據

#include<iostream>
#include<algorithm>
using namespace std;const int N=1010;int n;
int a[N], f[N];int main()
{cin>>n;for (int i = 1; i <= n; i++) cin>>a[i];for (int i = 1; i <= n; i++){f[i] = 1;  //初始化，只有a[i]一個數for (int j = 1; j < i; j++)//j<i,a[j] < a[i]，max三個條件作為集合劃分為選或不選的依據if (a[j] < a[i])f[i] = max(f[i], f[j] + 1);}int res = 0;for (int i = 1; i <= n; i++) res = max(res, f[i]);//在dp數組內找maxcout<<res;return 0;
}

Q2：變式（加大數據量）

最終的邏輯上的候選最長子序列中越靠前的數字越小越好

?比如說3 8和1 8,1 8組合更好， 因為1和8之間的差距大，可以插入作為序列長度的數字多，所以在dp數組中可以不記錄3 8這個序列，把這一部分冗余去除。

那么換成與上述狀態表示的集合“所有以第i個數結尾的上升子序列集合”的邏輯來講，相同長度最后結尾的數字越小越好。

需要存儲：所有長度對應的最小結尾值，定義一個q[N]數組

?

上圖自變量是長度，應變量是該序列對應最小結尾值

可以證明是該數組是單調遞增的，因為假設長度為5的序列最小結尾值為10，長度為6的序列最小結尾值為8，那我是不是其實可以把長度為5的序列的10去掉換為8，把長度為6的序列的8去掉換為10啊？所以這種情況如果說代碼邏輯存的對的話是不應該發生的，故嚴格遞增。

核心過程：在q數組中找小于a[i]的最大的一個數，我們在邏輯上是為了將a[i]插入到該邏輯子序列（候選的最長上升子序列，是我們的目標但是我們不存它的全部，只在q對應長度下標位置存它的最后一位數）的結尾，而q數組正好是存儲的該子序列結尾元素，所以最后實際的操作就是“覆蓋”掉q數組該位置的元素， 以實現邏輯上的邏輯子序列的后插操作。同樣也不用擔心“重復覆蓋”問題，比如q[1]是否被覆蓋兩次以上從而造成邏輯子序列邏輯長度與q下標不對應的情況，因為我們在小于a[i]、最大這里對我們找的q下標位置做了確切的定位，只要在q中存在元素比q[1]大的元素q[j]或者邊界位置空白，那么a[i]就會跳過q[1]被放在q[j]位置或者右邊界處。

#include<iostream>
#include<algorithm>
using namespace std;const int N=100010;
int a[N],q[N];//a存輸入進來的數，q每個數組元素位置i的意義為序列長度為i的序列結尾的最小值
int n;int main()
{cin>>n;for(int i=0;i<n;i++)cin>>a[i];int len=0;//q中的元素個數q[0]=-2e9;//哨兵for (int i = 0; i < n; i++){int l=0,r=len;while (l < r)//二分過程，在q中找小于a[i]的最大的一個數{int mid = l + r + 1 >> 1;//+1是為了邊界 if (q[mid] < a[i]) l = mid;else r = mid - 1;}len = max(len, r + 1);q[r + 1] = a[i];//不用擔心覆蓋問題，找到了就該覆蓋，在邏輯上是個后插操作//邏輯上在招的對應上升子序列后插，存儲上是結尾數字，那就是要賦值給q[r + 1]}cout<<len;return 0;
}