求最长升序（降序）子数列

      第一次接触到求最长升序（降序）子数列这个知识是在导弹拦截问题中，导弹拦截问题如下：

题意：一种导弹拦截系统的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉

到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高

度，计算这套系统最多能拦截多少导弹？

分析：

     因为每一次拦截弹道的发射都不能高于前一发拦截导弹的高度，敌国导弹按照顺序袭来，此时我们需要观察敌国所有导弹的高度，

设定最佳的第一枚拦截导弹高度，尽可能的拦截更多的导弹。

例如敌国导弹共6颗，高度分别为：389；207；155；300；299；170；158；65

分析可知当我们最多可以拦截到六颗导弹（389；300；299；172；158；65）即就是求出最长子不升序子序列。

求解求最长升序（降序）子数列：

我们使用动态规划的思想来解决这个问题，用数组a[n]来存储原数组，在生成一个数组b[n]，b[i]来记录在前i个数据中存在的最长升序子序列的长度，b[i]也可以理解为：在前i个数据中以b[i]结尾所有子序列中最长子序列的长度。

最长升序子序列c++代码如下（降序代码改动在注释中给出）：

#include <iostream>

using namespace std;

int main(){    

int n;    //数据个数

int answer=0;    

cout << "请输入数组长度：" << endl;    

cin>>n;   

int a[n];   // 储存数据数组

int b[n];  //  动态规划辅助数组

cout << "请录入数组数据" << endl;    

for(int i=0;i<n;++i)

{

cin>>a[i];        

b[i]=1;    // 每个数据都至少可以构成长度为一的子序列

}

for(int i=1;i<n;++i) // 第一个数据子序列长度只可能为1，所以从第二个数据开始扫描

{

    for(int j=0;j<i;++j) //检查每个数前面所有数据

    {

        if(a[j]<a[i]) //若a[j]<a[i]，则有可能使以a[i]结尾的升序子序列长度加（！！求降序是用>号）

        {

        if(b[j]+1>b[i]) //遍历之前所有数据，找出b[i]的最大值

            {

            b[i]=b[j]+1;

            }

        }

    }

}

for(int i=0;i<n;++i) //在数组b中找出最大的b[i],即就是最长的升序子序列长度。

{

if(b[i]>answer)

    {

    answer=b[i];

    }

}

cout<<"最长升序子序列的长度为："<<answer<<endl;

return 0;

}