longest-increasing-subsequence

要求数组中严格递增的最长公共子序列,解题思路可以从简单到复杂逐步展开。以下是逐步深入的解题思路:

1. 暴力求解

  • 思路: 最简单的方式就是直接穷举数组的所有子序列,并检查这些子序列是否是严格递增的。找到所有严格递增的子序列后,选择其中长度最长的一个。
  • 步骤:
    1. 生成数组的所有可能的子序列。
    2. 对每个子序列进行判断,检查是否严格递增。
    3. 返回长度最长的严格递增子序列。
  • 缺点: 这种方法的时间复杂度是指数级的 \(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 来存储以每个元素为结尾的最长递增子序列的长度。
  • 步骤:
    1. 初始化一个 dp 数组,其中 dp[i] 表示以 arr[i] 结尾的最长递增子序列的长度。初始时,dp[i] 为 1(因为每个元素单独形成一个子序列)。
    2. 对于每个元素 arr[i],检查之前的所有元素 arr[j](其中 j < i),如果 arr[j] < arr[i],则 dp[i] = max(dp[i], dp[j] + 1)
    3. 最后 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] 表示以第 i 个元素结尾的最长严格递增子序列的长度。

  • arr[j] < arr[i] )表示严格递增的条件。

  • 初始时

    初始条件是:

$$ 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;

// 初始化dp数组,每个元素初始值为1
for (int i = 0; i < n; i++) {
dp[i] = 1;
}

// 填充dp数组
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));
}
}

时间复杂度分析

  1. 外层循环:我们需要遍历整个数组,这个循环的次数是 n(数组的长度)。

  2. 内层循环:对于每个元素,我们需要回头查看它之前的所有元素,以找到可以形成递增子序列的元素。在最坏的情况下(比如数组是降序的),我们需要查看当前元素之前的所有元素。

  3. 对于第 i 个元素,内层循环需要执行 i 次。

因此,总的操作次数是:

$$ 1 + 2 + 3 + ... + (n-1) + n $$
这是一个等差数列的求和,其结果为:
$$ \frac{n(n+1)}{2} $$

所以,时间复杂度为 \(O(n^2)\)

3. 二分查找优化的动态规划

  • 思路: 上述动态规划算法可以通过二分查找进一步优化。这个方法结合了动态规划和二分查找,利用一个辅助数组 tails 来维护当前找到的最长递增子序列的最小末尾元素。

  • 步骤:

    1. 初始化一个空的 tails 数组,用来维护长度为 i+1 的子序列的最小末尾元素。
    2. 对数组的每个元素 arr[i],使用二分查找在 tails 中找到大于等于 arr[i] 的第一个位置,然后用 arr[i] 替换这个位置的元素。
    3. 如果 arr[i]tails 中所有元素都大,则将 arr[i] 添加到 tails 末尾。
    4. tails 的长度即为最长递增子序列的长度。
  • 优点: 这种方法的时间复杂度为 O(n log 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
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. 最后,堆栈的数量即为最长递增子序列的长度。

代码

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) 的时间复杂度。

总结

  1. 暴力求解:适合理解问题本质,适用于小规模数据。
  2. 动态规划:效率较高,适合中等规模数据,容易理解和实现。
  3. 二分查找优化的动态规划:效率最高,适合大规模数据。实现起来稍微复杂一些,但时间复杂度是最优的。

数学分析子序列个数

为了理解暴力解法,用数学的思想思考子序列的所有情况。

证明一

  1. 首先,让我们定义什么是子序列:
    子序列是从原始序列中通过删除某些元素(也可以不删除)后得到的新序列,且保持原始顺序不变。

  2. 对于数组中的每个元素,我们有两种选择:

    • 将其包含在子序列中
    • 不将其包含在子序列中
  3. 由于每个元素都有这两种独立的选择,我们可以使用乘法原理。

  4. 对于长度为n的数组,总的选择数量为:

    \(\underbrace{2 \times 2 \times 2 \times \cdots \times 2}_{n\text{ 次}}\)

  5. 这可以表示为2的n次方:

    \(2^n\)

  6. 因此,子序列的总数量为\(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} \),要么不包含。

  • 不包含 \( a_{n+1} \) 的子序列:这些子序列与长度为 \( n \) 的数组 \( A \) 的子序列相同,因此共有 \( 2^n \) 个。

  • 包含 \( a_{n+1} \) 的子序列:这些子序列是通过在长度为 \( n \) 的数组 \( A \) 的每一个子序列后面添加元素 \( a_{n+1} \) 得到的,因此也有 \( 2^n \) 个。

因此,长度为 \( n+1 \) 的数组 \( A’ \) 的子序列数量为:

$$ 2^n + 2^n = 2 \times 2^n = 2^{n+1} $$