题目:这是一个经典的LIS(即最长上升子序列)问题,请设计一个尽量优的解法求出序列的最长上升子序列的长度。给定一个序列A及它的长度n(长度小于等于500),请返回LIS的长度。

测试样例:[1,4,2,5,3],5返回:3

思路:所谓LIS问题即LongestIncresingSeuenceL最长递增子序列,注意子序列并不要求连续,即子序列不等于连续子序列。首先要理解什么是最长递增子序列以及如何求最长递增子序列,例如对于序列1,4,2,5,3,8,6,9。里面的递增子序列有很多,1,4是递增子序列,1,4,5,8,9是递增子序列,4,5,8,9是递增子序列,4,5,6,9是递增子序列。那么何为最长递增子序列呢?首先,对于1,4这种显然不是最长递增子序列,只有当后面不再有更大的元素时的序列才叫作最长子序列,因此对于最长子序列,前面不应该有更小的元素,后面不应该有更大的元素。我们对序列从局部到整体进行考虑,先考虑前面部分的序列,例如1,4,2,5然后考虑把3加上去后会最长递增子序列会发生怎样的变化,3加上后与前面比3更小的元素2构成了子序列,即对于以2为终点的序列,加上3后使得序列右增加了1,且此时序列的终点变成了3。于是思路是:从前向后求出以index为终点的序列的最长递增子序列长度:

Index=0时maxLength=1;   【1】

Index=1时maxLength=2;  【1,4】

Index=2时maxLength=2;  【1,2】

Index=3时maxLength=3;  【1,4,5】【1,2,5】

Index=4时maxLength=3;  【1,2,3】

Index=5时maxLength=4;  【1,4,5,8】【1,2,5,8】【1,2,3,8】

Index=6时maxLength=4;  【1,4,5,6】【1,2,5,6】【1,2,3,6】

Index=7时maxLength=5;  【1,4,5,8,9】【1,2,5,8,9】【1,2,3,8,9】【1,4,5,6,9】【1,2,5,6,9】【1,2,3,6,9】

对于index,在求它的最长递增子序列时是先将arr[index]与之前的元素进行逐一比较,找出小于arr[index]的元素中maxLength最长的值,于是对于元素index,以它为终点的最长递增子序列长度就是在maxLength上+1,并将此结果保存在一个数组dp[index]中以便后面复用。

即从index=0开始逐一计算以arr[index]为最长递增序列终点的最长递增子序列长度,将其保存在dp[index]中,在计算后面任意一个index为终点的最长递增序列长度时,遍历前面的所有元素的maxLength,找出元素arr[i]<arr[index]的元素中的最大的maxLength值,将arr[index]加在这个序列上构成以arr[index]为终点的最长递增子序列,以此类推,当index到达结尾时所有子序列长度遍历结束,扫描整个数组dp[]里面的最大值就是最大递增子序列的长度(最后一个元素index并不一定是最长子序列的终点元素,即可能最长递增子序列 在一个序列的中间位置)

动态规划:

①创建动态规划数组保留每个计算结果,这里只需要一维数组dp[n];

②先计算dp[]中第一个位置的值,即dp[0],即以arr[0]为终点的最长递增子序列的最大子序列长度是1;

③从前往后计算dp[]中的每一个位置的值;注意递推关系的使用;

④扫描dp[],里面的最大值就是所求结果;

 

import java.util.*;
//最长递增子序列问题:动态规划
public class LongestIncreasingSubsequence {
    public int getLIS(int[] A, int n) {
        //特殊输入
        if(A==null||A.length<=0) return 0;
        //①创建动态规划数组dp[]来存放计算结果
        int[] dp=new int[n];
        //②计算第1个结果dp[0]
        dp[0]=1;
        //③从后往前计算每一个结果
        for(int i=1;i<n;i++){
            int maxLength=0;
            for(int j=0;j<i;j++){
                if(A[j]<A[i]){
                    maxLength=Math.max(dp[j],maxLength);
                }
            }
            //如果没有A[j]<A[i]说明没有比A[i]更小的值,于是它自己组成序列,长度应该为1;
            dp[i]=maxLength+1;
        }
        //④返回结果:dp[]中的最大值
        int res=0;
        for(int i=0;i<n;i++){
            res=Math.max(dp[i],res);
        }
        return res;
    }
}