300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1

Solution

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
class Solution {
    // 主方法，计算最长递增子序列的长度
    public int lengthOfLIS(int[] nums) {
        int n = nums.length; // 获取数组的长度
        int ans = 0; // 用于存储最长递增子序列的长度
        int[] f = new int[n]; // 初始化一维数组 f，用于存储以每个元素结尾的最长递增子序列的长度

        // 遍历数组中的每个元素
        for (int i = 0; i < n; i++) {
            // 遍历当前元素之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果前面的某个元素 nums[j] 小于当前元素 nums[i]
                if (nums[j] < nums[i]) {
                    // 更新 f[i]，取当前 f[i] 和 f[j] 的较大值
                    f[i] = Math.max(f[i], f[j]);
                }
            }
            // 当前元素的最长递增子序列长度加 1
            ans = Math.max(ans, ++f[i]);
        }

        // 返回最长递增子序列的长度
        return ans;
    }
}

还有优化空间：

f[i]表示末尾元素为nums[i]的LIS长度

g[i]表示长度为i+1的IS的末尾元素的最小值

可以依次遍历nums数组，同时用二分查找找到 nums 数组中第一个大于或等于 x 的位置索引 j，根据j的大小决定是否拓展数组

image-20240518184418598

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 int lengthOfLIS(int[] nums) {
    int ng = 0; // 变量 ng 表示 g 数组的长度，初始为 0
    
    // 遍历输入数组中的每个元素
    for (int x : nums) {
        // 找到 nums 数组中第一个大于或等于 x 的位置索引 j
        int j = lowerBound(nums, ng, x);
        // 将 nums[j] 更新为 x
        nums[j] = x;
        // 如果 j 等于 ng，说明没有找到大于或等于 x 的位置，ng 加 1
        if (j == ng) {
            ng++;
        }
    }
    // 返回 ng，表示最长递增子序列的长度
    return ng;
}

// 二分查找方法，寻找数组前 n 个元素中第一个大于或等于 x 的位置
private int lowerBound(int[] nums, int n, int x) {
    int left = 0, right = n;
    // 使用二分查找在数组的前 n 个元素中寻找第一个大于或等于 x 的位置
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] < x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}