? ? ??第一次接觸到求最長(zhǎng)升序（降序）子數(shù)列這個(gè)知識(shí)是在導(dǎo)彈攔截問題中，導(dǎo)彈攔截問題如下：
題意：一種導(dǎo)彈攔截系統(tǒng)的第一發(fā)炮彈能夠到達(dá)任意的高度观谦，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉
到敵國(guó)的導(dǎo)彈來襲兄一。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)识腿，因此有可能不能攔截所有的導(dǎo)彈出革。輸入導(dǎo)彈依次飛來的高
度，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈覆履？
分析：
? ? ?因?yàn)槊恳淮螖r截彈道的發(fā)射都不能高于前一發(fā)攔截導(dǎo)彈的高度蹋盆，敵國(guó)導(dǎo)彈按照順序襲來，此時(shí)我們需要觀察敵國(guó)所有導(dǎo)彈的高度硝全，
設(shè)定最佳的第一枚攔截導(dǎo)彈高度栖雾，盡可能的攔截更多的導(dǎo)彈。
例如敵國(guó)導(dǎo)彈共6顆伟众，高度分別為：389析藕；207；155凳厢；300账胧；299；170先紫；158治泥；65
分析可知當(dāng)我們最多可以攔截到六顆導(dǎo)彈（389；300遮精；299居夹；172败潦；158；65）即就是求出最長(zhǎng)子不升序子序列准脂。
求解求最長(zhǎng)升序（降序）子數(shù)列：
我們使用動(dòng)態(tài)規(guī)劃的思想來解決這個(gè)問題劫扒，用數(shù)組a[n]來存儲(chǔ)原數(shù)組，在生成一個(gè)數(shù)組b[n]狸膏，b[i]來記錄在前i個(gè)數(shù)據(jù)中存在的最長(zhǎng)升序子序列的長(zhǎng)度沟饥，b[i]也可以理解為：在前i個(gè)數(shù)據(jù)中以b[i]結(jié)尾所有子序列中最長(zhǎng)子序列的長(zhǎng)度。
最長(zhǎng)升序子序列c++代碼如下（降序代碼改動(dòng)在注釋中給出）：
#include <iostream>
using namespace std;
int main(){? ??
int n; ? ?//數(shù)據(jù)個(gè)數(shù)
int answer=0;? ??
cout << "請(qǐng)輸入數(shù)組長(zhǎng)度：" << endl; ? ?
cin>>n; ??
int a[n]; ? // 儲(chǔ)存數(shù)據(jù)數(shù)組
int b[n]; ?// ?動(dòng)態(tài)規(guī)劃輔助數(shù)組
cout << "請(qǐng)錄入數(shù)組數(shù)據(jù)" << endl;? ??
for(int i=0;i<n;++i)
{
cin>>a[i];? ? ? ??
b[i]=1; ? ?// 每個(gè)數(shù)據(jù)都至少可以構(gòu)成長(zhǎng)度為一的子序列
}
for(int i=1;i<n;++i) // 第一個(gè)數(shù)據(jù)子序列長(zhǎng)度只可能為1湾戳，所以從第二個(gè)數(shù)據(jù)開始掃描
{
? ? for(int j=0;j<i;++j) //檢查每個(gè)數(shù)前面所有數(shù)據(jù)
? ? {
? ? ? ? if(a[j]<a[i]) //若a[j]<a[i]贤旷，則有可能使以a[i]結(jié)尾的升序子序列長(zhǎng)度加（！院塞！求降序是用>號(hào)）
? ? ? ? {
? ? ? ? if(b[j]+1>b[i]) //遍歷之前所有數(shù)據(jù)遮晚，找出b[i]的最大值
? ? ? ? ? ? {
? ? ? ? ? ? b[i]=b[j]+1;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
for(int i=0;i<n;++i) //在數(shù)組b中找出最大的b[i],即就是最長(zhǎng)的升序子序列長(zhǎng)度性昭。
{
if(b[i]>answer)
? ? {
? ? answer=b[i];
? ? }
}
cout<<"最長(zhǎng)升序子序列的長(zhǎng)度為："<<answer<<endl;
return 0;
}
