此题来源于草狼所给网站，题目如下：
Problem Description
FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.

Input
Input contains data for a bunch of mice, one mouse per line, terminated by end of file.

The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.

Two mice may have the same weight, the same speed, or even the same weight and speed.

Output
Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],..., m[n] then it must be the case that

W[m[1]] < W[m[2]] < ... < W[m[n]]

and

S[m[1]] > S[m[2]] > ... > S[m[n]]

In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.

Sample Input
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

Sample Output
4
4
5
9
7
个人理解：
此题的核心问题为：给出一组数字5，2，3，6，4，7
求去掉最少个数的数字使得该数字串满足从小到大排列。如去掉5，6或者5，4均能满足要求。请输出一组去掉最少数字后满足要求的数字串即可！欢迎大家讨论！说说自己的算法思路都行，我觉得此题挺有意思的所以贴上来了！请大家解决这个最长串数字即可!

我有个思路如下
把数字串 按从小到大排列  然后计算和原串的相对位置。把相对位置最远的那个去掉，然后检查是否满足，如不满足则从新排序计算下去掉下一个相对位置最远的，再检查...直到出现满足条件的数字串
如 原串 5，2，3，6，4，7
   排列 2，3，4，5，6，7
   偏移 1，1，2，3，1，0
则先去掉5得2，3，6，4，7不满足，继续操作
   原串 2，3，6，4，7
   排列 2，3，4，6，7
   偏移 0，0，1，1，0
继续去掉4得2，3，6，7满足条件！我不确定这样总能得到最长的数字串....

[ 本帖最后由 zglieren303 于 2010-4-11 20:01 编辑 ]

去掉所有比后一个大的数不就行了。

你把问题也想得太简单了！
如7，8，3，9
按你的做法 先去掉8，再去掉7 剩下的3，9显然不是答案！
或者把你会说那去掉所有比前一个数字小的数就行了。那对于5，2，3，6就会得5，3，6-->5，6也不是正确的答案
以前其实我也想过  统计每一个数字并记录下后面有多少比它小（或者大）的数字个数，每次去掉其中最大（或者小）的那个。如此往复直到满足要求的解出现。但是我觉得相比较可能我二楼的那个算法会更能得到正确答案！

1，把数字串用数字a【】存放。
2，把a【i】>a【i+1】比较， 把a【i】点删掉，a【i】<a【i+1】比较，执行2，
3，最后的a[],就是要求的数字串

其实这个没有什么选择，第一个数字定了，又是由小到大，所以数字的删除就固定了。

楼上的思路计算的结果只能满足从小到大的要求，而不能满足最核心的：这个子串是最长的！而且你的算法大部分情况下都求不出最长的那个....

写了一个代码，输入数字串并以-1111结束。如

代码如下：
#include<stdio.h>
#define MAX 100
struct number {
    int value;
    int flag;
    int smaller;
    int bigger;
};
struct number numbers[MAX];
int length,left;
int isPass();
int killTheBigger();
int print();
int main()
{ int i;
length=0;
for(i=0;i<MAX;i++)
 {scanf("%d",&numbers[i].value);
  if(numbers[i].value==-1111)break;
  numbers[i].flag=1;
  length++;
  numbers[i].smaller=0;
  numbers[i].bigger=0;
 }
 left=length;
 while(!isPass())
 killTheBigger();
 print();
 return 0;
}
int killTheBigger()
{int current,i,max,position;
 for(i=0;i<length;i++)
 {numbers[i].smaller=0;numbers[i].bigger=0;}
 for(current=0;current<length;current++)
 {if(numbers[current].flag==0)continue;
  for(i=0;i<current;i++)
  if(numbers[i].flag==1 && numbers[i].value>=numbers[current].value)numbers[current].bigger++;
  for(i=current+1;i<length;i++)
  if(numbers[i].flag==1 &&numbers[i].value<=numbers[current].value)numbers[current].smaller++;
 }
  i=0;
  while(numbers[i].flag==0)i++;
  for(max=(numbers[i].smaller>numbers[i].bigger? numbers[i].smaller:numbers[i].bigger),position=i;i<length;i++)
  {if (numbers[i].flag==0)continue;
   if(max<(numbers[i].smaller>numbers[i].bigger? numbers[i].smaller:numbers[i].bigger))
   {max=(numbers[i].smaller>numbers[i].bigger? numbers[i].smaller:numbers[i].bigger);position=i;}
  }
  numbers[position].flag=0;
  left--;
  return 0;
 }
int isPass()
{
int i,istrue=1,m,n;
 for(i=0;i<length;)
 {while(numbers[i].flag==0)i++;
  if(i==length-1)break;
  m=numbers[i].value;i++;
 while(numbers[i].flag==0)i++;
  if(i==length)break;
  n=numbers[i].value;
  if(m>=n){istrue=0;break;}
}
  return istrue;
}
int print()
{int i;
 printf("the largest substring's length:%d\none example is:",left);
 for(i=0;i<length;i++)
 if(numbers[i].flag==1)printf("%d ",numbers[i].value);
return 0;
}
我并不确定所有的情况都会输出正确的结果，我用的是贪心算法！

最长递增数列问题。复杂度O（nlogn）.

[此贴子已经被作者于2021-5-17 15:12编辑过]