【每日算法】最长递增子序列

学而不思则罔，思而不学则殆

---

题目

题目：一个数组的最长递增子序列的个数
比如：数组[4, 9, 9, 19, 17, 12, 19, 5, 3, 5]
最长递增子序列是[4,9,12,19],长度为4

解法1 排序+最长公共子序列法LCS

其中排序最快的时间复杂度为$$O(nlogn)$$
LCS的时间复杂度为$$O(n^2)$$
所以整体时间负责度为$$O(n^2)$$
空间空间复杂度，由于需要辅助空间，所以为$$O(n^2)$$
具体实现欢迎可以查看:【每日算法】最长公共子序列LCS，这里就不在过多介绍。

解法2 动态规划法（时间复杂度O(N^2))

假设长度为n的数组S{s0,s1,s2…sn-1},则假定以ai结尾的数组序列的最长子序列长度为L[i],则:
$$L[i]=\{\begin{array}{ll}max(L[j])+1& \text{if j<i and s[j] < s[i]}\end{array}$$
也就是说，我们需要遍历在j之前的所有位置i(从0到j-1)，找出满足条件s[j]<s[i]的L(i)，求出max(L[j])+1即为L[i]的值。最后，我们遍历所有的L[i]（从0到n-1），找出最大值即为最大递增子序列。时间复杂度为$$O(N^2)$$
同理我们可以得出最长非递减子序列的递推公式：
$$L[i]=\{\begin{array}{ll}max(L[j])+1& \text{if j<i and s[j] <= s[i]}\end{array}$$

最长递减子序列的递推公式：
$$L[i]=\{\begin{array}{ll}max(L[j])+1& \text{if j<i and s[j] > s[i]}\end{array}$$
最长非递增子序列的递推公式：
$$L[i]=\{\begin{array}{ll}max(L[j])+1& \text{if j<i and s[j] >= s[i]}\end{array}$$

参考

public class LISDemo {
    public static void main(String[] args) {
        int[] ints1 = create(10, 20);
        int maxLis = lis(ints1);
        System.out.println("ints1:" + Arrays.toString(ints1));
        System.out.println("maxLis:" + maxLis);
    }

    private static int[] create(int num, int range) {
        int[] ints = new int[num];
        Random random = new Random();
        for (int i = 0; i < num; i++) {
            ints[i] = random.nextInt(range);
        }
        return ints;
    }


    private static int lis(int[] values) {
        //辅助数组- 表示i结尾的数据LIS
        int[] flag = new int[values.length];
        Arrays.fill(flag, 1);
        flag[0] = 1;
        //记录最大
        int currentMax = 0;
        for (int i = 1; i < values.length; i++) {
            int current = values[i];
            for (int flagIndex = i - 1; flagIndex >= 0; flagIndex--) {
                //如果当前位置数据比比较点小
                if (current > values[flagIndex]) {
                    int tmpFlag = flag[flagIndex] + 1;
                    if (tmpFlag > flag[i]) {
                        flag[i] = tmpFlag;
                    }
                }
            }

            //记录最大长度
            if (flag[i] > currentMax) {
                currentMax = flag[i];
            }
        }
        System.out.println("flag:" + Arrays.toString(flag));
        return currentMax;
    }
}

范例1

flag:[1, 1, 1, 2, 3, 3, 2, 4, 1, 2]
ints1:[14, 6, 6, 12, 17, 13, 7, 19, 2, 7]
maxLis:4

最长的是4，对应的序列为[6,12,13,19]

范例2

flag:[1, 1, 1, 1, 2, 2, 3, 4, 3, 5]
ints1:[15, 13, 2, 0, 8, 7, 12, 16, 12, 19]
maxLis:5

最长的是5，对应的序列为[0，8,12,16,19]或者[2,7,12,16,19]或者[2,8,12,16,19]或者[0,7,12,16,19]

该算法主要是理解递推公式。

本文地址：https://blog.csdn.net/yuzhangzhen/article/details/109611178