然后讲讲我的想法： 有结论不上升子序列的个数=最长上升子序列的长度.....至于为什么，在下面讲
上代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 class P 6 { 7 public: 8 int x,id; //x为数的大小，id为标记 9 }a[1000]; 10 int main() 11 { 12 int n,i,j,number,minn,b[1000]; 13 while(~scanf("%d",&n)) 14 { 15 memset(a,0,sizeof(a)); 16 for(i=0;i<n;i++) 17 scanf("%d",&a[i].x); 18 number=0; 19 printf("LIS: "); 20 for(i=0;i<n;i++) 21 if(a[i].id==0) //未被标记 ① 22 { 23 number++; //组数+1 24 a[i].id=number; //标记为组的编号 ② 25 minn=a[i].x; //更新最小值 26 for(j=i+1;j<n;j++) 27 { 28 if(a[j].id==0 && a[j].x<=minn) //未被白标记且不大于最小值 ③ 29 { 30 a[j].id=number; //标记为组编号 31 minn=a[j].x; //更新最小值 ④ 32 } 33 } 34 } 35 for(i=n-1,j=number;i>=0;i--) 36 { 37 if(a[i].id==j) //找到满足编号及大小的数 ⑤ 38 { 39 b[j]=a[i].x; 40 j--; //组编号-1 41 } 42 } 43 for(i=1;i<=number;i++) ⑥ 44 printf("%d ",b[i]); 45 printf(" LIS number:"); 46 printf("%d ",number); 47 } 48 return 0; 49 }
从第一个数据开始，找到第一个未被标记的数①，记录组编号，并标记为组编号②，再在这个数之后找未被标记的<=它的数③，标记为组编号，并更新最小值④，循环。
最后从最后一个数扫描，标记=编号--⑤的第一个数就记录下来，在就是正序输出这些数⑥。
例： 数组：9 10 6 7 2 1 8 4 3 5
组的编号： 1 2 1 2 1 1 3 2 2 3
从最后一个扫描，找到第一个编号为3的数：5
再找编号为2 的数：3
再找编号为1的数：1
所以顺序输出为1 3 5，长度3
从上得知，每一组出一个数组成最长上升子序列，这就是为什么最长上升子序列的长度=不上升子序列的个数了~~~
本来只是用来做俄罗斯套娃这道题，后来发现做导弹拦截系统这道题也可以，再发现就是求最长上升子序列，后来想办法把上升序列打出来，中间当然有很多错误，两个人慢慢讨论，一点点完善，修改，测试，就有个这段代码。
还是不懂的翻到最前面，戳进那个网页~(≧▽≦)/~啦啦啦