问题描述

测试代码

解决思路

代码实现

总结

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

小葵

2024-06-12

🏷

java面试题

问题描述

编写一个函数,该函数接受一个整数列表作为参数,计算这个列表的最长递增子序列(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) ,获取更多有趣的编程挑战题和技术干货!

友情链接:

Copyright© 2024 杭州园中葵科技有限公司 版权所有