Java数据结构算法(最长递增序列二分查找)

前言:

最长递增子序列（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: