前言:

最长递增子序列（Longest Increasing Subsequence, LIS）是指在一个给定的序列中，找到一个最长的子序列，使得这个子序列中的元素是单调递增的。子序列不要求在原序列中连续。

实现原理

• 使用一个 tails 列表，其中 tails[i] 存储长度为 i+1 的所有递增子序列中最后一个元素的最小值。
• 对于每个元素 num，使用二分查找找到 num 在 tails 中的插入位置。如果 num 大于 tails 中的所有元素，则将 num 添加到 tails 的末尾，否则更新相应位置的元素。
• tails 的长度即为最长递增子序列的长度。

实现代码

import java.util.ArrayList;
import java.util.List;

public class LongestIncreasingSubsequence {

    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        List<Integer> tails = new ArrayList<>();

        for (int num : nums) {
            int pos = binarySearch(tails, num);
            if (pos < tails.size()) {
                tails.set(pos, num);
            } else {
                tails.add(num);
            }
        }

        return tails.size();
    }

    private static int binarySearch(List<Integer> tails, int key) {
        int low = 0, high = tails.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (tails.get(mid) < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

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

QA1: