要求数组中严格递增的最长公共子序列,解题思路可以从简单到复杂逐步展开。以下是逐步深入的解题思路:
1. 暴力求解
- 思路: 最简单的方式就是直接穷举数组的所有子序列,并检查这些子序列是否是严格递增的。找到所有严格递增的子序列后,选择其中长度最长的一个。
- 步骤:
- 生成数组的所有可能的子序列。
- 对每个子序列进行判断,检查是否严格递增。
- 返回长度最长的严格递增子序列。
- 缺点: 这种方法的时间复杂度是指数级的 \(O(2^n)\),对于大规模的输入,计算成本极高,效率非常低。
代码
非递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| import java.util.ArrayList; import java.util.List;
public class LongestIncreasingSubsequence { public static int longestIncreasingSubsequenceBruteForce(int[] arr) { int maxLen = 0; int n = arr.length; List<Integer> subsequence = new ArrayList<>(); for (int i = 0; i < (1 << n); i++) { List<Integer> current = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) > 0) { current.add(arr[j]); } } if (isStrictlyIncreasing(current)) { maxLen = Math.max(maxLen, current.size()); } } return maxLen; }
private static boolean isStrictlyIncreasing(List<Integer> list) { for (int i = 1; i < list.size(); i++) { if (list.get(i) <= list.get(i - 1)) { return false; } } return true; }
public static void main(String[] args) { int[] arr = {3, 10, 2, 1, 20}; System.out.println("Length of longest increasing subsequence: " + longestIncreasingSubsequenceBruteForce(arr)); } }
|
递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| public class LongestIncreasingSubsequence { private int maxLen = 0; public int lengthOfLIS(int[] nums) { backtrack(nums, 0, new ArrayList<>()); return maxLen; } private void backtrack(int[] nums, int start, List<Integer> current) { if (start == nums.length) { if (isIncreasing(current)) { maxLen = Math.max(maxLen, current.size()); } return; } backtrack(nums, start + 1, current); current.add(nums[start]); backtrack(nums, start + 1, current); current.remove(current.size() - 1); } private boolean isIncreasing(List<Integer> list) { for (int i = 1; i < list.size(); i++) { if (list.get(i) <= list.get(i - 1)) { return false; } } return true; } }
|
2. 动态规划(Dynamic Programming, DP)
- 思路: 可以使用动态规划来优化这个问题。我们用一个数组
dp
来存储以每个元素为结尾的最长递增子序列的长度。
- 步骤:
- 初始化一个
dp
数组,其中 dp[i]
表示以 arr[i]
结尾的最长递增子序列的长度。初始时,dp[i]
为 1(因为每个元素单独形成一个子序列)。
- 对于每个元素
arr[i]
,检查之前的所有元素 arr[j]
(其中 j < i
),如果 arr[j] < arr[i]
,则 dp[i] = max(dp[i], dp[j] + 1)
。
- 最后
dp
数组中的最大值就是最长递增子序列的长度。
- 优点: 时间复杂度为 \(O(n^2)\),比暴力求解要高效很多。
状态转移方程
对于最长递增子序列(LIS)问题,令 ( dp[i] ) 表示以第 ( i ) 个元素结尾的最长严格递增子序列的长度,则状态转移方程为:
$$
dp[i] = \max\left(1, \max_{0 \leq j < i} \{ dp[j] + 1 \mid \text{if } arr[j] < arr[i] \}\right)
$$
其中:
$$
dp[i] = 1, \quad \forall i \in [0, n-1]
$$
这是因为每个元素自身就构成一个长度为1的递增子序列。
$$
LIS=( \max(dp[0], dp[1], \ldots, dp[n-1]) )
$$
即
$$
LIS = \max_{0 \leq i < n} \{dp[i]\}
$$
即所有 dp[i] 中的最大值。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| public class LongestIncreasingSubsequence {
public static int longestIncreasingSubsequenceDP(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int n = arr.length; int[] dp = new int[n]; int maxLen = 1;
for (int i = 0; i < n; i++) { dp[i] = 1; }
for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; }
public static void main(String[] args) { int[] arr = {3, 10, 2, 1, 20}; System.out.println("Length of longest increasing subsequence: " + longestIncreasingSubsequenceDP(arr)); } }
|
时间复杂度分析
外层循环:我们需要遍历整个数组,这个循环的次数是 n(数组的长度)。
内层循环:对于每个元素,我们需要回头查看它之前的所有元素,以找到可以形成递增子序列的元素。在最坏的情况下(比如数组是降序的),我们需要查看当前元素之前的所有元素。
对于第 i 个元素,内层循环需要执行 i 次。
因此,总的操作次数是:
$$
1 + 2 + 3 + ... + (n-1) + n
$$
这是一个等差数列的求和,其结果为:
$$
\frac{n(n+1)}{2}
$$
所以,时间复杂度为 \(O(n^2)\)
3. 二分查找优化的动态规划
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| import java.util.Arrays;
public class LongestIncreasingSubsequence {
public static int longestIncreasingSubsequenceBinarySearch(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int n = arr.length; int[] tails = new int[n]; int size = 0;
for (int num : arr) { int left = 0, right = size; while (left < right) { int mid = (left + right) / 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) { int[] arr = {3, 10, 2, 1, 20}; System.out.println("Length of longest increasing subsequence: " + longestIncreasingSubsequenceBinarySearch(arr)); } }
|
4. “耐心排序”(Patience Sorting)
耐心排序是一种利用堆栈(或牌堆)来模拟排序过程的算法,其核心思想是将数组中的元素逐一放入堆栈中,每个堆栈顶部元素都比其下面的元素大,以此来找到最长递增子序列的长度。
下面是耐心排序算法求解 LIS 的步骤:
- 初始化一组空的堆栈。
- 遍历数组中的每个元素,将该元素放入适当的堆栈中。如果元素小于或等于堆栈的顶部元素,则将其放入该堆栈;如果元素大于堆栈顶部元素,则寻找下一个堆栈,直到找到合适的堆栈位置。
- 如果所有堆栈的顶部元素都大于当前元素,则创建一个新的堆栈,并将该元素放入。
- 最后,堆栈的数量即为最长递增子序列的长度。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| import java.util.ArrayList; import java.util.List; public class Solution { public int lengthOfLIS(int[] nums) { List<Integer> piles = new ArrayList<>(); for (int num : nums) { int pile = 0; int left = 0, right = piles.size(); while (left < right) { int mid = (left + right) / 2; if (piles.get(mid) >= num) { right = mid; } else { left = mid + 1; } } if (left == piles.size()) { piles.add(num); } else { piles.set(left, num); } } return piles.size(); } }
|
这段代码实际上和动态规划 + 二分查找的解法非常相似,都是通过二分查找来找到元素应该放置的位置,但是这里的实现是通过模拟“耐心排序”的过程来求解 LIS 的长度。这种方法同样具有 O(n log n) 的时间复杂度。
总结
- 暴力求解:适合理解问题本质,适用于小规模数据。
- 动态规划:效率较高,适合中等规模数据,容易理解和实现。
- 二分查找优化的动态规划:效率最高,适合大规模数据。实现起来稍微复杂一些,但时间复杂度是最优的。
数学分析子序列个数
为了理解暴力解法,用数学的思想思考子序列的所有情况。
证明一
首先,让我们定义什么是子序列:
子序列是从原始序列中通过删除某些元素(也可以不删除)后得到的新序列,且保持原始顺序不变。
对于数组中的每个元素,我们有两种选择:
由于每个元素都有这两种独立的选择,我们可以使用乘法原理。
对于长度为n的数组,总的选择数量为:
\(\underbrace{2 \times 2 \times 2 \times \cdots \times 2}_{n\text{ 次}}\)
这可以表示为2的n次方:
\(2^n\)
因此,子序列的总数量为\(2^n\)。
组合数学证明
子序列可以有0个元素、1个元素、2个元素,…,直到n个元素
对于k个元素的子序列(0 ≤ k ≤ n),我们有\(\binom{n}{k}\)种选择方式
根据二项式定理,我们有:
\(\sum_{k=0}^n \binom{n}{k} = (1+1)^n = 2^n\)
因此,我们从两个角度证明了长度为n的数组的子序列数量为\(2^n\)。
归纳法证明
为了更严谨,我们可以用数学归纳法来证明。
基例:\( n = 1 \)
当数组的长度 \( n = 1 \) 时,数组 \( A \) 中只有一个元素 \( a_1 \)。显然,子序列的数量为:
$$
2^1 = 2
$$
这两个子序列分别是:空子序列和包含 \( a_1 \) 的子序列。
归纳假设:
假设对于长度为 \( n \) 的数组,子序列的数量为 \( 2^n \)。
归纳步骤:
现在考虑长度为 \( n+1 \) 的数组 \( A’ \):
$$
A' = [a_1, a_2, \dots, a_n, a_{n+1}]
$$
对于这个新数组中的每个子序列,要么包含元素 \( a_{n+1} \),要么不包含。
因此,长度为 \( n+1 \) 的数组 \( A’ \) 的子序列数量为:
$$
2^n + 2^n = 2 \times 2^n = 2^{n+1}
$$