Java实现最长递增子序列算法

简介

最长递增子序列（Longest Increasing Subsequence，LIS）问题是在一个给定的序列中，找到一个子序列，使得这个子序列中的元素是递增的，并且这个子序列的长度是所有递增子序列中最长的。这是一个经典的动态规划问题，在计算机科学、数据分析等多个领域都有广泛的应用。本文将详细介绍如何使用Java实现最长递增子序列算法，帮助读者理解其原理并掌握实际应用。

目录

  1. 基础概念
    • 什么是最长递增子序列
    • 动态规划原理
  2. 使用方法
    • 暴力解法
    • 动态规划解法
  3. 常见实践
    • 数组中的最长递增子序列
    • 应用场景示例
  4. 最佳实践
    • 优化动态规划解法
    • 二分查找优化
  5. 小结
  6. 参考资料

基础概念

什么是最长递增子序列

给定一个整数序列 [10, 9, 2, 5, 3, 7, 101, 18]，它的一个递增子序列可以是 [2, 3, 7, 18]，而最长递增子序列是 [2, 3, 7, 101]，长度为 4。子序列不要求元素在原序列中是连续的。

动态规划原理

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为相对简单的子问题，然后保存子问题的解来避免重复计算，从而解决复杂问题的方法。对于最长递增子序列问题，我们定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。状态转移方程为：

[ dp[i] = \max_{0 \leq j < i, nums[j] < nums[i]}(dp[j]) + 1 ]

使用方法

暴力解法

暴力解法是通过枚举所有可能的子序列，然后判断每个子序列是否递增，并记录最长的递增子序列长度。这种方法的时间复杂度为 ( O(2^n) )，空间复杂度为 ( O(1) )。

public class LongestIncreasingSubsequenceBruteForce {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int maxLength = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > nums[i]) {
                    maxLength = Math.max(maxLength, helper(nums, i, j) + 1);
                }
            }
        }
        return maxLength;
    }

    private int helper(int[] nums, int start, int end) {
        if (start == end) {
            return 0;
        }
        int maxLength = 0;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] > nums[start]) {
                maxLength = Math.max(maxLength, helper(nums, i, end) + 1);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequenceBruteForce solution = new LongestIncreasingSubsequenceBruteForce();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(solution.lengthOfLIS(nums));
    }
}

动态规划解法

动态规划解法通过保存子问题的解，避免了重复计算，时间复杂度为 ( O(n^2) )，空间复杂度为 ( O(n) )。

public class LongestIncreasingSubsequenceDP {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxLength = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequenceDP solution = new LongestIncreasingSubsequenceDP();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(solution.lengthOfLIS(nums));
    }
}

常见实践

数组中的最长递增子序列

在一个整数数组中找到最长递增子序列是最常见的应用场景。上述代码示例已经演示了如何解决这个问题。

应用场景示例

在股票交易中，我们可以通过找到股票价格序列中的最长递增子序列，来确定一个股票价格持续上涨的最长时间段，从而辅助投资决策。

最佳实践

优化动态规划解法

我们可以通过二分查找进一步优化动态规划解法，将时间复杂度降低到 ( O(n \log n) )。我们维护一个数组 tails，其中 tails[i] 表示长度为 i + 1 的递增子序列的最小末尾元素。

public class LongestIncreasingSubsequenceOptimized {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] tails = new int[nums.length];
        int size = 0;
        for (int num : nums) {
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = num;
            if (left == size) {
                size++;
            }
        }
        return size;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequenceOptimized solution = new LongestIncreasingSubsequenceOptimized();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(solution.lengthOfLIS(nums));
    }
}

二分查找优化原理

在上述代码中，我们通过二分查找在 tails 数组中找到第一个大于等于 num 的元素位置 left，如果 left 等于 size，说明 num 大于 tails 数组中的所有元素，我们将 num 追加到 tails 数组中，size 加 1。否则，我们用 num 替换 tails[left]，因为我们希望长度为 left + 1 的递增子序列的末尾元素尽可能小，这样后续更容易找到更长的递增子序列。

小结

本文详细介绍了Java实现最长递增子序列算法的基础概念、使用方法、常见实践以及最佳实践。暴力解法虽然简单直观，但效率低下，适用于小规模数据。动态规划解法通过保存子问题的解，提高了效率，适用于中等规模数据。而通过二分查找优化的动态规划解法，将时间复杂度降低到 ( O(n \log n) )，能够处理大规模数据。读者可以根据实际情况选择合适的算法来解决最长递增子序列问题。

参考资料