Java实现最长递增子序列问题

最长递增子序列（Longest Increasing Subsequence, LIS）是指在一个给定的数列中找到最长的子序列，使得该子序列中的元素按顺序递增。例如，在数列 [1, 7, 2, 8, 3, 4] 中，最长的递增子序列是 [1, 2, 3, 4]，其长度为4。

在解决这个问题时，我们定义一个函数 foo(k) 表示以第 k 个元素结尾的最长递增子序列的长度。对于每个元素，我们需要检查它之前的所有元素，如果当前元素大于之前的某个元素，则可以将当前元素添加到之前的递增子序列中，形成一个新的更长的递增子序列。

以下是使用 Java 实现的原始方法：

public class LISDemo {    public static void main(String[] args) {        int[] arr = new int[10];        Random random = new Random();        for (int i = 0; i  arr[i]) {                maxLength = Math.max(maxLength, tempLength + 1);            } else {                maxLength = Math.max(maxLength, tempLength);            }        }        return maxLength;    }}

这种方法的时间复杂度为 O(2^n)，因为每次调用 foo 函数都会递归地调用自身多次，导致大量的重复计算。随着输入数组长度的增加，计算时间呈指数级增长，效率极低。

为了解决这个问题，我们可以使用记忆化搜索（Memoization）技术来避免重复计算。具体做法是使用一个哈希表存储已经计算过的子问题的结果，当再次遇到相同的子问题时，直接从哈希表中读取结果，而不需要重新计算。以下是改进后的代码：

public class LISDemo {    public static void main(String[] args) {        int[] arr = new int[31];        Random random = new Random();        for (int i = 0; i  memo = new HashMap<>();        public LIS(int[] arr) {            this.arr = arr;        }        public int foo() {            return foo(arr, arr.length - 1);        }        private int foo(int[] arr, int end) {            if (memo.containsKey(end)) return memo.get(end);            if (end == 0) {                memo.put(0, 1);                return 1;            }            int maxLength = 0;            for (int i = 0; i  arr[i]) {                    maxLength = Math.max(maxLength, tempLength + 1);                } else {                    maxLength = Math.max(maxLength, tempLength);                }            }            memo.put(end, maxLength);            return maxLength;        }    }    private static int foo(int[] arr, int end) {        if (end == 0) return 1;        int maxLength = 0;        for (int i = 0; i  arr[i]) {                maxLength = Math.max(maxLength, tempLength + 1);            } else {                maxLength = Math.max(maxLength, tempLength);            }        }        return maxLength;    }}

通过这种优化，程序的执行效率得到了显著提升，即使对于较长的输入数组，也能在合理的时间内完成计算。