用Java实现LIS(最长递增子序列)算法

问题描述

编写一个函数，该函数接受一个整数列表作为参数，计算这个列表的最长递增子序列(LIS)的长度，这个也是动态规划中常见的问题。

举一个典型的场景：

用来查找股票价格的最大增长，比如股票价格是[12, 13, 11, 14, 15, 16, 10, 9, 8, 7]，股票价格的最大增长是[12, 13, 14, 15, 16]，最大增长的长度是5。

通过查找出股票价格的最大增长，可以将这部分数据进行标注，找出股票价格的连续增长的趋势。

测试代码

int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
assertEqual(lis(arr), 6, "1");

int[] arr1 = { 12, 13, 11, 14, 15, 16, 10, 9, 8, 7 };
assertEqual(lis(arr1), 5, "2");

int[] arr2 = { 10, 9, 2, 3, 4, 1 };
assertEqual(lis(arr2), 3, "3");

解决思路

在最长递增子序列（Longest Increasing Subsequence，简称 LIS）的定义中，子序列的元素不需要在原数组中连续。它们可以在原数组中的任何位置，只要它们的相对顺序保持不变。对于数组 {10, 22, 9, 33, 21, 50, 41, 60, 80}，其最长递增子序列为 {10, 22, 33, 50, 60, 80}。这个子序列并不包括 41，因为 41 小于它前面的元素50。

在这个子序列中，每个元素都大于它前面的元素，所以它是递增的。并且这个子序列的长度（6）是所有递增子序列中最长的，所以它是最长递增子序列。

在计算最长递增子序列时，我们并不是简单地从数组的开始到结束检查每个元素。相反，我们使用一个动态规划的方法，对于每个元素，我们都检查它前面的所有元素，看看是否可以通过添加当前元素来延长一个已经存在的递增子序列。

这就是为什么 41 没有被包括在最长递增子序列中的原因，因为它不能延长任何已经存在的递增子序列。

代码实现

public static int lis(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int res = 1;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

完整代码请参考: Lis.java

总结

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是一个非常的数据分析的算法，很多时候我们需要拟合数据，找出数据的增长趋势，这个算法就可以帮助我们找出数据的增长趋势。

所有的后端面试常见的问题，我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群，一起学习和进步。

编程交流群

欢迎大家关注入职啦 (公众号: ruzhila) ，获取更多有趣的编程挑战题和技术干货！