算法-最长递增子序列LIS

朱雀 2022-05-23 05:27 177阅读 0赞

【题目】

给定数组arr，返回arr的最长递增子序列LIS。

【思路】

设dp\[i\]表示在以arr\[i\]这个数结尾的情况下，LIS长度。

动态规划思想：最后一个数arr\[N-1\]的LIS长度：设j属于集合\[0， N-1)

(1)若arr\[N-1\] < arr\[j\]，则dp\[N-1\]==1。含义是arr\[N-1\]小于前面所有数，最长子递增序列只有自己一个数。

(2)若arr\[N-1\] > arr\[j\]，则dp\[N-1\]==max\{dp\[j\]\} + 1。含义是arr\[N-1\]大于前面某些数，最长递增子序列等于这些数中dp最大值加一。

public class LIS {
        public static void main(String[] args) {
            int[] arr = {2, 1, 5, 3, 6, 4, 8, 9, 7};
            int[] dp = getdpl(arr);
            int[] lis = lis(arr, dp);
            for (int i : lis) {
                System.out.print(i + " ");
            }
        }
        public static int[] lis(int[] arr, int[] dp) {
            int len = 0;//LIS长度
            int index = 0;//LIS最后一个元素的索引
            for (int i = 0; i < dp.length; i++) {
                if (dp[i] > len) {//迭代求出dp数组中的最大值，即LIS长度，同时记录LIS最后一个元素索引
                    len = dp[i];
                    index = i;
                }
            }
    
            //
            int[] lis = new int[len];//用来记录LIS
            lis[--len] = arr[index];//LIS的最后一个元素
            for (int i = index; i >= 0; i--) {//从后往前反推
                if (arr[i] < arr[index] && dp[i] + 1 == dp[index]) {//判断是否属于LIS的方法
                    lis[--len] = arr[i];//记录到LIS中
                    index = i;//记录此索引
                }
            }
            return lis;
        }
        public static int[] getdpl(int[] arr) {
            int[] dp = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {//遍历数组，计算数组中每个元素的LIS长度
                dp[i] = 1;//默认为1
                for (int j = 0; j < i; j++) {//从前面已经计算过的所有小于当前元素的元素中取一个最大的
                    if (arr[i] > arr[j]) {//如果前面有元素小于当前元素，那么更新dp值
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp;
        }
    }

算法复杂度为O(n^2)