题目描述

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

输入格式

输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

输出格式

最长单调递增子序列的长度

整体思路

对输入数组num[]进行一次遍历，利用dp[]保存num[]从开始到当前位置的最长单调递增子序列。

设当前求得的序列长度为q，则对于每一个num[i]，若num[i]>dq[q]，将num[i]加入dp[]中；
若num[i]<dp[q]，查找dp[q]中比num[i]大的第一个的位置，更新该位置的值，查找过程用二分法实现。

for(int i=1;i<n;i++)
    {

        if(num[i]>dp[q])
        {
            q++;
            dp[q]=num[i];
        }
        else if(num[i]<dp[q])
        {
            int k=bfind(dp,q+1,num[i]);
            if(k!=-1)
            {

                dp[k]=num[i];

            }    
        }
    }

可以这样理解，dp[]数组前面存的数字越小，后面比该序列中数大的数就越可能多；另外，由于本题目只要求求得最长单调递增子序列的长度，所以在求dp数组的过程中，尽管每次更新可能导致所选序列不是num[]的子序列，但是序列长度是不被影响的。

总结

这道题目和平时做到的动态规划不太一样，dp数组不是存数量，而是存找到的序列（虽然也不是真正的序列···），以后可以注意一下这种想法。