动态规划之最长上升子序列（入门版）

最长上升子序列不是最大上升子序列，思想一样但结果可能不一样

        比如：序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。

现在我们要解决的问题就是在给定的数组中找出最长上升子序列：先给一个栗子

给定的数组 a[7] = {1,6,4,2,3,9,8}

思想：这里用到的是一个自底向上的寻找最优子结构的的思想。粗俗来说：如果你想要得到七个数里面的最长子序列，你可以先找前6个数里面的最长子序列，同理，你又必须得找前5个数里面的最长子序列，直到子序列为1

大体的步骤是这样的

d[i]:用数组d 来存储前第 i 个数的最长子序列,i 表示的就前几个数

毫无疑问        {1}  -------------------------------d[1]=1 : 表示第一个数他的最长子序列是1      {1}

                   {1,6}  --------------------------------d[2]=d[1]+1=2 : 表示前两个数中，最长上升子序列为2   {1,6}

                {1,6,4}  --------------------------------d[3]=d[1]+1=2 : 因为4 < 6 所以不能用 d[2]+1,但 1<4 所以 是 d[1]+1。 {1,6},{1,4} 等

             {1,6,4,2} ---------------------------------d[4]=d[1]+1=2 : 4和6 都大于2 所以不能用d[2],d[3]。 {1,6},{1,4} 等

         {1,6,4,2,3}  ---------------------------------d[5]=d[4]+1=3 : 3 >2 所以 可以d[4]+1=2+1=3  。 {1,2,3}

      {1,6,4,2,3,9} ----------------------------------d[6]=d[5]+1= 4 : d[5]+1=3+1=4  。 {1,2,3,9}

   {1,6,4,2,3,9,8} ----------------------------------d[7]=4   ：        {1,2,3,9} 或者{1,2,3,8}

如果上面的步骤能看明白，只是在思想上是通的了，现在就差用代码来实现我们的思想：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;// 数组的长度
    while(cin>>n)
    {
        // a ：待输入数组
        // d ：用于保存第i个数字时的最长子序列
        // m : 用于保存d[i]数组中的最长子序列的个数
        int a[1001]={0},m=-1,d[1001]={0};
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        d[1]=1; //数组长度为一的时候，最长子序列也是一
        if(n<2)
            cout<<d[1]<<endl;//数组长度为一的时候，最长子序列也是一
        else
        {
            for(int i=2;i<=n;i++)// 循环遍历第i个数字
            {
                for(int j=1;j<i;j++)// 遍历前i个数
                {
                    if(a[j]<a[i])   // 如果比第j个数比第i个数小：存在递增关系
                        d[i] = max(d[i],d[j]); //得出第i个数之前的最长上升子序列
                }
                d[i]=d[i]+1;// 在第i个之前加上自身 等于第i个数的最长上升子序列
                m = max(d[i],m); // 得到d[i] 中最大得数
            }
        }
        cout<<m<<endl;
    }
    return 0;
}

好，终于讲完了了，自己也是一步一步慢慢啃得，可能在表达上还是有欠缺，体谅一下哈，下一篇，准备讲如何在优化；

如果有兴趣，请看下一篇