《面试题甄选》17.最长的递增子序列

《面试题精选》17.最长的递增子序列

［题目］从给定序列中找出最长的子序列所含元素的个数，如｛7，2，3，1，5，8，9，6｝,的最长递增子序列为｛2，3，5，8，9｝，则返回个数5。

［分析］：这道题感觉挺难的，用到了动态规划，感觉动态规划度挺难的，关于动态规划可以参照前面的博客：详解动态规划，动态规划与贪心。

正如这两篇博客中讲到的，解决动态规划问题，关键点在于找状态和状态方程。那么这道题怎么来找呢，老套路，举例分析嘛。

就拿题目中的例子来举，对于序列｛7，2，3，1，5，8，9，6｝，找到最长的序列，你首先会怎么做，肯定是逐个分析，比如我们插入2时要跟前面插入的7比较，插入5时要跟前面的4个数做比较，下图中列中的数逐个与他之前的数(行中的数)做比较。表格内部表示增长序列元素的个数。

如分析7时，个数为1；

分析2时，因为比7小，不能插入，所以个数仍为1

分析3时，逐个比较7和2，因为比7小，所以不能和7组合，那么个数为1；因为比2大，所以可以和2组合，2中最长序列个数为1，在此基础上加1，则3与2组合时最长序列个数为2。

分析1时，因为比7，2，3都小，所以都不能组合，这样的话，如果存在1的话，最长序列最多为1。

分析5时，因为比7小，所以为1，比2大，所以为2；比3大，因为3中最长为2，所在基础上加1，最长为3。

一次类推下去，你就发现了，状态和状态方程。

结合下面的图分析

          

上面是网上别人的答案，

public class MaxLength{
    public static void main(String args[]){
        for(int i=0 ;i<1;i++){
            int[] array = {7,2,3,1,5,8,9,6} ;
            System.out.println(maxLength(array)) ;
        }
    }
    public static int maxLength(int[] array){
        int[] maxArray = new int[array.length] ;
        maxArray[0] = 1 ;
        int max = 0 ;
        for(int i=1;i<array.length;++i){
            for(int j=0;j<i;++j){
                if(array[i]>array[j]&&max<maxArray[j]){
                    max = maxArray[j] ;
                }
            }
            maxArray[i] = max +1 ;
        }
        int num = 1 ;
        for(int i=0;i<maxArray.length;++i){
            if(maxArray[i]>num) num = maxArray[i] ;
        }
        return  num ;        
    }
}

总结：对于动态规划的题还要多做。仔细研究下面两篇博客。

             详解动态规划，动态规划与贪心