0%

最长上升子序列O(nlogn)

发表于 分类于 阅读次数： Valine： 1.9k 2 分钟

1. 问题

对于给定的序列，求该序列中最长上升子序列长度
如：
8 2 7 1 9 10 1 4 3 5

最终输出4（最长上升子序列为[2，7，9，10]）

2. 分析

2.1 方法一

很容易想到的就是O(n^2)的算法：
f[i]标识前i个元素中的最长不下降子序列的长度，则

f[i] = max(f[j]) +1, 0<j<i && a[j]<a[i]

2.2 方法二

换个思路，用d[i]标识以长度为i，最长上升子序列中元素的最小值，拿上面的例子来说
8 2 7 1 9 10 1 4 3 5

8
d[1] = 8 （目前为止，长度为1，最长上升子序列最小值当然是8）

8 2
d[1] = 2 （因为2比8小，同样长度为1，最小值需要更新，因为2比8更优）

8 2 7
d[1,2] =2, 7 （我们发现d[1]<a[3] = 7,直接长度加1，并把7添加到d中）

8 2 7 1
d[1,2] = 1,7 （为啥1的位置比2靠后，也能更新2？因为对于长度为1的最长不下降子序列，1作为结尾是最小的）

8 2 7 1 9
d[1,2,3] = [1,7,9]

8 2 7 1 9 10
d[1,2,3,4] = [1,7,9,10]

8 2 7 1 9 10 1
d[1,2,3,4] = [1,7,9,10]

8 2 7 1 9 10 1 4
d[1,2,3,4] = [1,4,9,10]

8 2 7 1 9 10 1 4 3
d[1,2,3,4] = [1,3,9,10]

8 2 7 1 9 10 1 4 3 5
d[1,2,3,4] = [1,3,5,10]
（为啥5的位置比9靠后，也能更新9？因为对于长度为3的最长不下降子序列，5作为结尾是最小的）

我们发现d数组并不是保存最终的最长上升子序列。假如已经计算出两个状态i，j满足A[i]i且i>j）来说，i并不会比j差——如果j满足Aj<Ak的条件，i也满足。换句话说，如果我们只保留i，一定不会丢失最优解。因此，对于相同的d值，只需要保留A数组中最小的一个即可。

对于A数组中的所有元素 A[i] 
1）若d[len] < a[i]，则len = len + 1, d[len] = A[i]
2）否则在d[1...len]中找到最大的t, 满足d[t]<A[i]，此时用A[i]更新d，即d[t] = A[i]
步骤1时间复杂度是O(n)，步骤2，因为d是递增的，所以可以用二分查找，时间复杂度是O(nlogn)，因此整个算法复杂度为O(nlogn)

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>  
#include<cstring>  
#define MAXN 100000  
  
int a[MAXN],ans[MAXN],len;  
int binary_search(int i){  
    int left,right,mid;  
    left=0,right=len;  
    while(left<right){  
        mid = left+(right-left)/2;  
        if(ans[mid]>=a[i]) right=mid;  
        else left=mid+1;  
    }  
    return left;
}  
  
int main()  
{  
    int T,N,i,j,k;  
    scanf("%d",&T);  
    while(T--){  
        scanf("%d",&N);  
        for(i=1; i<=N; ++i)  
            scanf("%d",&a[i]);  
          
        ans[1] = a[1];  
        len=1;  
        for(i=2; i<=N; ++i){  
            if(a[i]>ans[len])  
                ans[++len]=a[i];  
            else{  
                int pos=binary_search(i);
                ans[pos] = a[i];  
            }
            for (int j=1 ; j<=len;j++) {
            	printf("%d ",ans[j]);  
            }
            printf("\n");
           
        }  
        printf("%d\n",len);  
    }  
    return 0;  
}

输入如下：

1
2
3
1 
10 
8 2 7 1 9 10 1 4 3 5

输出结果为：

1
2
3
4
5
6
7
8
9
10
2 
2 7 
1 7 
1 7 9 
1 7 9 10 
1 7 9 10 
1 4 9 10 
1 3 9 10 
1 3 5 10 
4

和我们分析结果是一致的。