掌握Java最长递增子序列（LIS）算法详解（小白也能学会的动态规划实战教程）

方法一：动态规划（O(n²) 时间复杂度）

这是最直观的方法。我们定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。

状态转移方程如下：

if (nums[j] < nums[i]) {    dp[i] = Math.max(dp[i], dp[j] + 1);}

完整 Java 代码实现如下：

public class LongestIncreasingSubsequence {    public static int lengthOfLIS(int[] nums) {        if (nums == null || nums.length == 0) return 0;                int n = nums.length;        int[] dp = new int[n];        Arrays.fill(dp, 1); // 每个元素至少构成长度为1的子序列                for (int i = 1; i < n; i++) {            for (int j = 0; j < i; j++) {                if (nums[j] < nums[i]) {                    dp[i] = Math.max(dp[i], dp[j] + 1);                }            }        }                // 找出dp数组中的最大值        int maxLength = 1;        for (int len : dp) {            maxLength = Math.max(maxLength, len);        }        return maxLength;    }        public static void main(String[] args) {        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};        System.out.println("最长递增子序列长度: " + lengthOfLIS(nums)); // 输出: 4    }}

方法二：二分查找优化（O(n log n) 时间复杂度）

如果你追求更高效率，可以使用“贪心 + 二分查找”的方法。核心思想是维护一个“潜在递增序列”的数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小尾部元素。

每当遇到一个新数字，我们用二分查找找到它在 tails 中的位置，并尝试替换或扩展该数组。

import java.util.Arrays;public class LISOptimized {    public static int lengthOfLIS(int[] nums) {        int[] tails = new int[nums.length];        int size = 0;                for (int x : nums) {            // 二分查找 x 应该插入的位置            int left = 0, right = size;            while (left < right) {                int mid = left + (right - left) / 2;                if (tails[mid] < x) {                    left = mid + 1;                } else {                    right = mid;                }            }            tails[left] = x;            if (left == size) size++;        }        return size;    }        public static void main(String[] args) {        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};        System.out.println("最长递增子序列长度: " + lengthOfLIS(nums)); // 输出: 4    }}

总结

通过本教程，你已经掌握了两种求解Java最长递增子序列的方法：

• 基础版：动态规划，时间复杂度 O(n²)，适合理解原理；
• 进阶版：贪心 + 二分查找，时间复杂度 O(n log n)，适合处理大数据。

无论你是准备面试，还是学习动态规划算法，LIS 都是一个绝佳的入门案例。建议你动手敲一遍代码，加深理解！

记住关键词：Java最长递增子序列、动态规划算法、Java算法教程、最长上升子序列。