2020年3月17日 最长的单调自增子序列

最长的单调自增子序列

问题描述

给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4.

想法

利用动态规划：
dp[i]为 以A[i]结尾的子序列的最长递增长度
因此A{5， 6， 7， 1， 2， 8} 来说
dp[0] = 1, {5}
dp[1] = 2 ,{5,6}
dp[2] = 3, {5,6,7}
dp[3] = 1 ,{1}

...

因此动态转移方程为 dp[i] = max{dp[0]+1,dp[1]+1,...dp[i]（值为1),其中要满足，值要比当前dp[i]小

数组A {5， 6， 7， 1， 2， 8}

dp数组为：【1，2，3，1，2，4】

解释一下，4为结尾为8的最长子序列。

public int getLIS(int[] arr, int n) {
        if(arr==null||arr.length<=0) return 0;

        //创建dp数组
        int[] dp=new int[arr.length];
        dp[0]=1;

        //用于记录最长的长度
        int maxLen = 1;
        for(int i=1;i<arr.length;i++){
            //每次都需要置1
            dp[i] =1;
            for(int j=i-1;j>=0;j--){
            //找到比当前arr[i] 要小的
                if (arr[j] < arr[i])
                    dp[i] = Math.max(dp[i],dp[j]+1);
            }
            maxLen = Math.max(dp[i],maxLen);
        }
        return maxLen;
    }