Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2407516
  • 博文数量: 392
  • 博客积分: 7040
  • 博客等级: 少将
  • 技术积分: 4138
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-17 13:03
个人简介

范德萨发而为

文章分类

全部博文(392)

文章存档

2017年(5)

2016年(19)

2015年(34)

2014年(14)

2013年(47)

2012年(40)

2011年(51)

2010年(137)

2009年(45)

分类:

2009-12-20 23:16:26

Stock Exchange
Submit: 137   Accepted:43
Time Limit: 5000MS  Memory Limit: 65536K
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
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);
    }
}
阅读(1575) | 评论(1) | 转发(0) |
0

上一篇:如何学习内核

下一篇:二分查找 boj1028

给主人留下些什么吧!~~

chinaunix网友2010-02-12 15:46:12

用你的方法做了一下,发现方法二是有问题的,当然思路没有问题,但在二分查找的时候没有考虑D[mid]==num的情况,这样当序列是1 1 1 1的时候就会输出4,而不是1,所以当D[mid]==num时,直接front=mid;break;这样就不会出现问题了。 不知道我说的对不对,菜鸟意见