Java实战 - 查找最长递增子序列_业界新闻

发布时间:2024-08-03 13:37

阅读量:0

作者：逍遥Sean
简介：一个主修Java的Web网站\游戏服务器后端开发者
主页：https://blog.csdn.net/Ureliable
觉得博主文章不错的话，可以三连支持一下~ 如有疑问和建议，请私信或评论留言！

前言
在计算机科学中，找到一个序列中最长递增子序列（Longest Increasing Subsequence, LIS）的长度是一个经典的问题，具有广泛的应用。本文将介绍如何使用动态规划（Dynamic Programming）算法来解决这个问题，并通过 Java 代码实现。

查找最长递增子序列

什么是最长递增子序列（LIS）？

最长递增子序列是指在一个序列中，找到一个最长的子序列，使得子序列中的元素按照递增顺序排列。例如，在序列 [10, 22, 9, 33, 21, 50, 41, 60, 80] 中，一个最长递增子序列可以是 [10, 22, 33, 50, 60, 80]，长度为 6。

动态规划解决方案

动态规划是解决最长递增子序列问题的有效方法。我们可以定义一个数组 dp，其中 dp[i] 表示以序列中第 i 个元素结尾的最长递增子序列的长度。

算法步骤：

初始化：创建一个长度与原始序列相同的 dp 数组，初始值为 1，因为每个单独的元素本身就是一个长度为 1 的递增子序列。
状态转移：对于每个元素 nums[i]，遍历其前面的每个元素 nums[j]（j < i），如果 nums[j] < nums[i]，则更新 dp[i] = max(dp[i], dp[j] + 1)。这表示如果能将 nums[i] 接在 nums[j] 后面形成更长的递增子序列，则更新 dp[i]。
求解：遍历整个 dp 数组，找到其中的最大值，即为整个序列的最长递增子序列的长度。

Java 实现代码：

下面是用 Java 实现动态规划解决最长递增子序列问题的代码示例：

public class LongestIncreasingSubsequence {      public static int findLengthOfLIS(int[] nums) {         if (nums == null || nums.length == 0) {             return 0;         }                  int n = nums.length;         int[] dp = new int[n];         dp[0] = 1; // 初始条件，单个元素的长度为 1                  int maxLen = 1; // 最长递增子序列的长度至少为 1                  for (int i = 1; i < n; i++) {             dp[i] = 1; // 每个元素本身的长度至少为 1             for (int j = 0; j < i; j++) {                 if (nums[j] < nums[i]) {                     dp[i] = Math.max(dp[i], dp[j] + 1);                 }             }             maxLen = Math.max(maxLen, dp[i]);         }                  return maxLen;     }      public static void main(String[] args) {         int[] nums = {10, 22, 9, 33, 21, 50, 41, 60, 80};         int lisLength = findLengthOfLIS(nums);         System.out.println("Length of Longest Increasing Subsequence: " + lisLength);     } }

解释和运行示例：

findLengthOfLIS 方法：这个方法接受一个整数数组 nums，并返回最长递增子序列的长度。通过两层循环，外层遍历每个元素，内层遍历其之前的元素，更新 dp 数组。
main 方法：在 main 方法中，我们展示了如何使用 findLengthOfLIS 方法找到序列 [10, 22, 9, 33, 21, 50, 41, 60, 80] 的最长递增子序列的长度，并将结果打印出来。