NYOJ214

单调递增子序列(二)

时间限制：1000 ms | 内存限制：65535 KB

难度：4

描述

给定一整型数列{a₁,a₂...,a_n}（0<n<=100000），找出单调递增最长子序列，并求出其长度。

如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。

输入

有多组测试数据（<=7）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的下一行里有n个整数，表示数列中的所有元素.每个整形数中间用空格间隔开（0<n<=100000）。
数据以EOF结束。
输入数据保证合法（全为int型整数）！

输出

对于每组测试数据输出整形数列的最长递增子序列的长度，每个输出占一行。

这个与单调递增子序列（一）有些不同，

（一）

在单调递增子序列一中，可以用一个数组保存当前位置之前的最大子序列长度，可以在一次遍历数组串，每次查询之前的数组小于当前数的最大值，这样的

时间复杂度就是0 + 1 + 2 + ... + n-1 = (n-1)*n/2 即O（n2）

例如输入：【2,3,1,2,3】

结果数组：【1,0,0,0,0】

　　　　　【1,2,0,0,0】

　　　　　【1,2,1,0,0】

　　　　　【1,2,1,2,0】

　　　　　【1,2,1,2,3】

结果是3

（二）的话可以用一个数组记录当前最大字符串长度，判断当前数与数组顶部的值大小，（1）如果大于数组顶的数则直接添加到尾部，数组长度加1

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（2）在数组中找到一个数，这个数是大于等于当前数的最小的

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（可以用二分法时间复杂度O(nlogn))

比如输入【2,3,1,2,3】

数组变化：

【2】

【2,3】

【1,3】

【1,2】

【1,2,3】

不过这个方法只能求出最大递增子序列长度

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int riseSubString(int a[], int n)
 5 {
 6     int i,l,r,m,s[100000],top = 0;
 7     if (n == 0)
 8         return 0;
 9     s[0] = a[0];
10     for (i=1; i < n; i++)
11     {
12         if (s[top] < a[i])
13             s[++top] = a[i];
14         else
15         {
16             l = 0;
17             r = top;
18             m = top / 2;
19             while ((l + 1) < r)         //二分，l与r间隔1时结束循环，再判断哪个是大于a[i]最小值
20             {
21                 if (a[i] <= s[m])
22                 {
23                     r = m;
24                     m = (r+l)/2;
25                 }
26                 else
27                 {
28                     l = m;
29                     m = (l+r)/2;
30                 }
31             }
32             if (s[l] > a[i])
33                 s[l] = a[i];
34             else
35                 s[r] = a[i];
36         }
37     }
38     return top + 1;
39 }
40 int main()
41 {
42     int a[100001];
43     int n,i;
44     while (scanf("%d",&n) != -1){
45         for (i=0; i < n; i++)
46             scanf("%d",&a[i]);
47         printf("%d
",riseSubString(a,n));
48     }
49     return 0;
50 }