傳送門

The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in ascending order. For example, the length of the LIS for { 15, 27, 14, 38, 26, 55, 46, 65, 85 } is 6 and the longest increasing subsequence is {15, 27, 38, 55, 65, 85}.

In this challenge you simply have to find the length of the longest strictly increasing sub-sequence of the given sequence.

Input Format

In the first line of input, there is a single number N. In the next N lines input the value of a[i].?

Constraints

1 ≤ N ≤ 10⁶

1 ≤ a[i] ≤ 10⁵?

Output Format

In a single line, output the length of the longest increasing sub-sequence.??

Sample Input

5 2 7 4 3 8

Sample Output

3

Explanation

{2,7,8} is the longest increasing sub-sequence, hence the answer is 3 (the length of this sub-sequence).

---

?

十分重要的基礎(chǔ)DP問題，是學(xué)習(xí)用各種方式優(yōu)化DP的一個很好的例子。

設(shè)DP[i]表示以a[i]結(jié)尾的LIS的長度，則狀態(tài)轉(zhuǎn)移方程為

DP[1]=1

DP[i] = max{DP[j], j<i && a[j]<a[i]} + 1, i>1

暴力求解復(fù)雜度為O(N^2)。

優(yōu)化1

考慮函數(shù)f(L):長度為 L 的 Increasing Sequence (IS) 的最小結(jié)尾, 顯然f(L)是單調(diào)遞增的。

從左到右掃描數(shù)組，維護動態(tài)的f(L)。

再看上面的DP方程，考慮我們維護的這個函數(shù)f(L)如何加速DP狀態(tài)轉(zhuǎn)移時所需的查詢。

顯然我們以a[i]為key，二分查詢f(L),得到max{L, f(L)<a[i]}

復(fù)雜度降為O(N*logN)

這一類DP優(yōu)化方法可歸納為 加速DP Query

#include<cstdio> #include<algorithm> using namespace std; const int MAX_N=1e6+10, oo=1e6; int A[MAX_N], f[MAX_N]; //二分法: binary_search(y, f()) //設(shè)有一個單調(diào)（不要求嚴格單調(diào)）的函數(shù)f() //可以在O(log N)的時間內(nèi)求解以下問題： //給定y,求滿足f(x)<=y/f(x)>=y的最大/最小的x // int binary_search(int y, int l, int r){ //y is the keyint mid;while(r-l>1){ //r is illegalmid=(l+r)>>1;if(f[mid]<y){l=mid;}else r=mid;}return l; }int main(){//freopen("in", "r", stdin);int N, ans=0;scanf("%d", &N);for(int i=1; i<=N; i++) scanf("%d", A+i);f[0]=0;for(int i=1; i<=N; i++) f[i]=oo;for(int i=1; i<=N; i++){int tmp=binary_search(A[i], 0, ans+1)+1;ans=max(ans, tmp);f[tmp]=min(f[tmp], A[i]);}printf("%d\n", ans);return 0; }

?優(yōu)化2

?具體地說，可把第一種優(yōu)化方式稱作單調(diào)性優(yōu)化。我們再考慮一種優(yōu)化方式。

仍觀察DP方程 DP[i]=max{DP[j], j<i && a[j]<a[j]} + 1

我們考慮用數(shù)據(jù)結(jié)構(gòu)加速查詢，查詢的鍵值 (key) 是a[i], ( 第一個條件 i<j 是自然滿足的), 對應(yīng)的value就是max{dp[j], a[j]<=a[i]}。我們把用于查詢的 <key, value> 維護成線段樹。其中key就是節(jié)點的L, R, 這樣<key, value> 查詢就是RMQ（Range Maximum Query)。

這樣可以優(yōu)化到O(NlogM)，M是a[i]的最大值，可通過NlogN的離散化優(yōu)化到NlogN (M比N大很多時才有必要離散化）。

#include<bits/stdc++.h> using namespace std; const int MAX_M=1e5+5, MAX_N=1e6+5; int ma[MAX_M<<2]; void insert(int id, int L, int R, int pos, int v){if(L==R){ma[id]=v;}else{int mid=(L+R)>>1;if(pos<=mid){insert(id<<1, L, mid, pos, v);}else{insert(id<<1|1, mid+1, R, pos, v);}ma[id]=max(ma[id<<1], ma[id<<1|1]);} } int query(int id, int L, int R, int l, int r){if(l<=L && R<=r) return ma[id];int mid=(L+R)>>1;int res=0;if(l<=mid){res=max(res, query(id<<1, L, mid, l, r));}if(r>mid){res=max(res, query(id<<1|1, mid+1, R, l, r));}return res; } int a[MAX_N]; int main(){//freopen("in", "r", stdin);int N;//single case, leave out initializationscanf("%d", &N);int rb;for(int i=0; i<N; i++) scanf("%d", a+i), rb=max(rb, a[i]);int ans=0;for(int i=0; i<N; i++){int tmp=query(1, 0, rb, 0, a[i]-1)+1;ans=max(ans, tmp);insert(1, 0, rb, a[i], tmp); //over-head }printf("%d\n", ans);return 0; }

這種優(yōu)化方法具體地可以稱作數(shù)據(jù)結(jié)構(gòu)優(yōu)化。
這種方法的弊端：

代碼量大、常數(shù)大

另外尤其注意插入操作

insert(1, 0, rb, a[i], tmp);

這個操作往往并沒有增大 (0, a[i]) 區(qū)間的最大值，但是這里每次更新都要深入到葉子節(jié)點，不能不說是一種冗余 (樹狀數(shù)組就很好地避免了這種冗余)。

其實沒必要用線段樹來維護查詢，注意到每次查詢的區(qū)間左端都是0，可用樹狀數(shù)組（Binary Indexed Tree， BIT）代替。

具體而言，BIT的每個節(jié)點維護對應(yīng)區(qū)間的最大值，更新與查詢的復(fù)雜度都是O(logM)總體復(fù)雜度為O（NlogM)。

#include<bits/stdc++.h> using namespace std; const int MAX_N=1e6+5, MAX_M=1e5+5; int bit[MAX_M], M; int a[MAX_N]; int query(int i){int res=0;while(i){res=max(res, bit[i]);i-=i&-i;}return res; } void modify(int i, int v){while(i<=M){if(bit[i]>=v) return;bit[i]=v;i+=i&-i;} } int main(){//freopen("in", "r", stdin);int N;scanf("%d", &N);M=0;for(int i=0; i<N; i++) scanf("%d", a+i), M=max(M, a[i]);int ans=0;int tmp;for(int i=0; i<N; i++){tmp=query(a[i]-1)+1;modify(a[i], tmp);ans=max(ans, tmp);}printf("%d\n", ans);return 0; }

BIT代碼短、速度快，可與二分查詢媲美。

P.S. 寫這篇隨筆時，專門考慮了如何用BIT維護prefix maximum。最初的想法是將prefix maximum維護（表示）成prefix sum，發(fā)現(xiàn)行不通。結(jié)論是自己學(xué)得太死，全不知變通。其實BIT和線段樹一樣，兩者的節(jié)點表示的都是區(qū)間，可以說沒有本質(zhì)差別。而我只知道BIT可維護prefix sum, 但對于BIT是如何維護prefix sum的卻不了然，所以不能靈活應(yīng)用。

Given a table of elements, it is sometimes desirable to calculate the?running total?of values up to each index according to some?associative?binary operation?(addition on integers, for example). Fenwick trees provide a method to query the running total at any index, in addition to allowing changes to the underlying value table and having all further queries reflect those changes.

轉(zhuǎn)載于:https://www.cnblogs.com/Patt/p/4693665.html

總結(jié)

以上是生活随笔為你收集整理的The Longest Increasing Subsequence (LIS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。