Java常见面试题分享-用Java实现LIS(最长递增子序列)算法

本文主要是介绍Java常见面试题分享-用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 没有被包括在最长递增子序列中的原因，因为它不能延长任何已经存在的递增子序列。