试题链接：最长上升子序列：POJ 2533
如何把这个问题分解成子问题呢？“求序列的前n个元素的最长上升子序列的长度F(n)”是一个子问题，但这样分解子问题，不具有“后无效性”。假设F(n)=x，但可能有多个序列满足F(n)=x。有的序列的最后一个元素比小，不能和形成一个更长的上升子序列······以后的事情（求F(n+1),F(n+2),···）受如何达到状态n的影响，因此F(n)这样的子问题分解方法不符合“后无效性”。

“后无效性”：当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，与之前是采取哪种手段或经过哪条路径演变到当前的若干个状态无关。

经过分析，发现“求以(k=1,2,3,······,N)为终点的最长上升子序列的长度”是一个合适的子问题，这里把一个上升子序列中最右边的那个数称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中最大的那个就是整个问题的解。

如上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置k就是“状态”，而状态k对应的“值”，就是以为“终点”的最长上升子序列。这个问题的状态一共有N个。状态定义出来后，转移方程就不难定义了。假定b(k)表示以ak为“终点”的最长上升子序列的长度，则

               b(1)=1;
               b(k)=Max{b(i):1<i<k且ai<ak且k!=1}+1

这个转移方程的意思是，b(k)的值就是在左边、“终点”数值小于且长度最大的那个上升子序列的长度在加1。因为左边任何“终点”小于的子序列，加上后就能形成一个更长的上升子序列。

实际实现时，可以不必编写递归函数，因为从b (1)就能推算出b(2)，有了b (1)和b (2)，就能推算出b (3)，以此类推。
7.3.3 代码

1.#include <cstdio>  
2.#include <iostream>  
3.#include <cmath>  
4.using namespace std;  
5.int a[1005];  
6.int b[1005];  
7.int main ()  
8.{  
9.    int n;  
10.    cin >> n;  
11.    for(int i=1;i<=n;i++) cin >> a[i];  
12.    b[1]=1;  
13.    for (int i=2;i<=n;i++)  
14.    {  
15.        int x=0;                     
16.        for (int j=1;j<i;j++)  
17.        {  
18.            if(a[j]<a[i])   x=max(b[j],x);  //这个地方的x可以不写，改成b[i]=max(b[i],b[j]);下面的b[i]=x+1改成b[i]++;
19.        }  
20.        b[i]=x+1;  
21.    }  
22.    int ans=0;  
23.    for (int i=1;i<=n;i++)  
24.    {  
25.        ans=max(ans,b[i]);  
26.    }  
27.    cout << ans << endl;  
28.    return 0;  
29.}