POJ 3903

Description

The world financial crisis is quite a subject. Some people are more relaxed while others are quite anxious. John is one of them. He is very concerned about the evolution of the stock exchange. He follows stock prices every day looking for rising trends. Given a sequence of numbers p1, p2,...,pn representing stock prices, a rising trend is a subsequence pi1 < pi2 < ... < pik, with i1 < i2 < ... < ik. John’s problem is to find very quickly the longest rising trend.

Input

Each data set in the file stands for a particular set of stock prices. A data set starts with the length L (L ≤ 100000) of the sequence of numbers, followed by the numbers (a number fits a long integer). White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

Output

The program prints the length of the longest rising trend. For each set of data the program prints the result to the standard output from the beginning of a line.

Sample Input

6 
5 2 1 4 5 3 
3  
1 1 1 
4 
4 3 2 1

Sample Output

3 
1 
1

Hint

There are three data sets. In the first case, the length L of the sequence is 6. The sequence is 5, 2, 1, 4, 5, 3. The result for the data set is the length of the longest rising trend: 3.

解题思路：1, 用一个数组存输入的最大升序，然后它的长度就是我们需要的答案

　　 2. 然后就是如何找到最大升序数组。这里可以分成两步：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1.判断当前数字时候大于前一数字

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　if(大于)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　把它放在数组后面

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　否则

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　通过2分法，判断它的大小应该放的位置

　　　　　　3. 循环一遍之后，数组存下来的就是最长升序了......

(对于有人问我，把数字替换到dp数组中，不是改变了它的位置吗？我的解释是，这里只是把一个更下的数去代替前面的数，不会改变最终输出的最长升序的长度，以及这样的替换是为了寻找最长的那个序列.... 不晓得我讲的行不行。╮(╯▽╰)╭ 语言表达能力有限，讲不下去了....)

代码如下：（去掉注释编译，就可以看见dp数组的整个变化，这样也许会有利于理解）

 1 #include <stdio.h>
 2 #include <string.h>
 3 int dp[100005],a[100005];
 4 int main()
 5 {
 6     int n,len,L,R,mid;
 7     while(scanf("%d",&n)==1)
 8     {
 9         for(int i=0; i<n; i++)
10             scanf("%d",&a[i]);
11         len=0;
12         dp[0]=-1;
13         for(int i=0; i<n; i++)
14         {
15             if(dp[len]<a[i])
16             {
17                 dp[++len]=a[i];
18                  /*for(int j=1;j<len;j++)
19                     printf("%d ",dp[j]);
20                 printf("%d
",dp[len]);*/
21             }
22             else
23             {
24                 L=1,R=len;
25                 while(L<=R)
26                 {
27                     mid=(L+R)/2;
28                     if(dp[mid]<a[i])
29                         L=mid+1;
30                     else
31                         R=mid-1;
32                 }
33                 dp[L]=a[i];
34                 /*for(int j=1;j<len;j++)
35                     printf("%d ",dp[j]);
36                 printf("%d
",dp[len]);*/
37             }
38         }
39         printf("%d
",len);
40 
41     }
42     return 0;
43 }