最长升序列 boj1407

Stock ExchangeSubmit: 137   Accepted:43Time Limit: 5000MS  Memory Limit: 65536KDescription
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
The program input is from a text file. 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). The program prints the length of the longest rising trend.
White spaces can occur freely in the input. The input data are correct and terminate with an end of file.


Output
For each set of data the program prints the longest rising trend 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
An input/output sample is in the table above. 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.


Source
Southeastern European 2008

最长升序列
第一种解法：O(n^2)时间复杂度，DP思想，具体见程序注释。

/* this solution is O(n^2) in time, got TLE, we will use a O(nlgn) algorithm in 1407b.c */
#include 
#include 

int sequence[100010];
int maxlen[100010];

void clear(void)
{
    int i = 0;
    for (i=0 ; i<100010 ; i++)
        maxlen[i] = 1;
}

int main(int argc, char *argv[])
{
    int L, i, j, max;
    while (EOF != scanf("%d", &L))
    {
        for (i=0 ; i            scanf("%d", &sequence[i]);
        clear();
        /* 这个循环是主要部分：对seq[i]，判断i前面的所有j最长升序列在加入seq[i]之后是否能增长maxlen[j]的数值，并取这些最长升序列的最大值，赋值给maxlen[i]
           maxlen[i]中存储的数值表示：在加入seq[i]这个数字后，所得到的最长升序列的长度 */
        for (i=1 ; i        {
            for (j=0 ; j            {
                if (sequence[i] > sequence[j] && (maxlen[j] + 1 > maxlen[i]))
                /* maxlen[i] storing the longest increasing sequence int positon i */
                maxlen[i] = maxlen[j] + 1;
            }
        }
        max = 1;
        /* 遍历maxlen[i]，其中的最大值即为最长升序列的长度 */
        for (i=0 ; i        {
            if (maxlen[i] > max)
                max = maxlen[i];
        }
        printf("%d\n", max);
    }
}

第二种解法：O(nlgn)时间复杂度。

    在上面的算法中，计算每一个Length[i]时都要找出最大的Length[j](j上面是转载的：其中的last数组就是下面我写的程序中的D数组。
特别要注意的是二分查找的程序，front返回的是小于target(所要查找的数值)的最大的位置+1。也就是说,如果D数组是0 3 6 8 9，要查找的数是7，那么查找后返回的值是3，也就是8的位置，现在可以替换8为7了(因为替换为一个更小的数，可以保证能得到最长的升序列)。如果需要查找的值大于9(假设为10)，那么需要增长D数组为0 3 6 8 9 10。
最后程序的输出为D数组的长度。

#include 

#define INT_MIN 0xffffffff;

int D[100010];

int bin_search(int front, int rear, int target)
{
    int mid;
    while (front <= rear)
    {
        mid = (front + rear) / 2;
        if (D[mid] < target)
            front = mid + 1;
        else
            rear = mid - 1;
    }
    return front;
}

int main(int argc, char *argv[])
{
    int L, i, num, last, k;
    while (EOF != scanf("%d", &L))
    {
        D[0] = INT_MIN; /* original state */
        last = 0;
        for (i=0 ; i        {
            scanf("%d", &num);
            /* 找到合适的位置，替换数据 */
            k = bin_search(0, last, num);
            D[k] = num;
            /* 如果需要，则增长数组 */
            if (k > last)
                last++;
        }
        if (0 == last)
            last = 1;
        printf("%d\n", last);
    }
}