111qqz的小窝

老年咸鱼冲锋!

最长上升子序列nlogn解法

首先回顾一下n^2的做法。
状态转移方程为dp[i] =max(1,dp[j]) (1=<j<=i-1&&a[i]>a[j])

然后我们发现,使得dp[i]得到同一个值的dp[j]可能有多个,那么选择哪个呢?
假设 x<y<i,a[x]<a[y],dp[x]==dp[y],那么我们选择x好还是y好呢?
显然是x好。为什么?因为选择x潜力大。因为可能在x,y之间存在一个z,满足a[x]<a[z]<a[y],如果选择a[y],就没有办法选择可能使长度更长的a[z]了。通俗得说。。我们要求的是最长上升子序列。。你一开始就弄那么大。。。后面还上哪上升去啊。。。长度小啊。。。

因此我们得出一个结论,对于dp[t]==k的所有t,要选择a[t]最小的,这样有更大可能得到更长的序列。

我们用g[k]表示所有dp[t]==k的t中,最小的a[t]的值。g[k] = min{A[t]} (dp[t] = k)

我们可以发现关于g的两个性质。

(1) g[k]肯定是单调不增的。因为求最小值嘛,肯

(2)g[1]<g[2]<g[3]….g数组是单调递增的。其实也很好理解,因为是求最长上升子序列,长度为i的序列的最末尾元素肯定要比长度为i+1的末尾的元素小,不然还怎么上升。

g数组初始为无穷大,g[i]表示还没有dp[t]==i的值。

 

1. 设当前已求出的最长上升子序列的长度为len(初始时为1),每次读入一个新元素x:

2. 若x>d[len],则直接加入到d的末尾,且len++;(利用性质2)

   否则,在g中二分查找,找到第一个比x小的数g[k],并g[k+1]=x,在这里x<=g[k+1]一定成立(性质1,2)

上面这段引用并没有很懂。。。。。回头再看。

 

 

 

模板如下。

说点什么

您将是第一位评论人!

提醒
wpDiscuz