最长单调递增子序列

设L={a1,a2,a3,...,an}是n个不同的实数组成的序列，L的递增子序列是这样一个序列： L`={ak1,ak2,ak3,...,akm}其中，k1<k2<k3<...<km，且ak1<=ak2<=ak3<=...<=akm 求：最大值m

分析：

设辅助数组b，b[i]表示以a[i]结尾的最长单调递增子序列的长度，则m的值为max{b[i]} 1<=i<=n;
状态转移方程：
b[1]=1;
b[i]=max{b[k]+1} 1<=i<=n;1<k<i;a[k]<=a[i];

C++实现

#include <iostream>
#define NUM 100
using namespace std;
int a[NUM];
int n;
int MaxSum()
{
    int b[NUM]={0};
    b[1]=1;
    int max=0;
    for(int i=2;i<=n;i++)
    {
        int k=0;
        for(int j=2;j<i;j++)
        {
            if(a[j]<=a[i]&&b[j]>k)
                k=b[j];
        }
        b[i]=k+1;
        if(max<b[i])
            max=b[i];
    }
    return max;
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<"单调递增序列最大长度："<<MaxSum()<<endl;
    return 0;
}