前言:

最長遞增子序列（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: