Recommendation: "Conquering Data Structures" Column: Completely conquering more than 50 kinds of data structures "Classical Graph Theory Algorithms" Column: Mastering more than 50 kinds of classical graph theory algorithms A programmer because of cerebral palsy, his body movements are slightly stiff, and he asks if he wants to write it on his resume. Some netizens suggested writing it, and some suggested not writing it, but in fact, if it doesn't affect the work, you can write it or not. But I think it's better to write it and make it clear that it won't affect your work. Because if you don't write it, if the company dislikes it during the interview, it will refuse for various reasons, and it will be very uncomfortable to run the interview in vain. -------------- here's today's algorithm problem-------------- Let's take a look at today's algorithm problem, which is LeetCode's 300th problem: the longest increasing subsequence. Problem description Source: LeetCode Question 300 Difficulty: Medium Give you an integer array nums to find the length of the longest strictly increasing subsequence. A subsequence is a sequence derived from an array that removes (or does not delete) the elements in the array without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]. Example 1: Input :nums = [10,9,2,5,3,7,101,18] Output :4 Explanation: The longest ascending subsequence is [2,3,7,101], so the length is 4. Example 2: Input :nums = [7,7,7,7,7,7,7,7] Output : 1 1 <= nums.length <= 2500 -10^4 <= nums[i] <= 10^4 Problem Analysis We just talked about "The Longest Increasing Subsequence" yesterday, using the solution of dynamic programming, here we use the method of binary search to solve this problem. If the current element is greater than the last element of the set, it means that the current element can form a longer ascending subsequence with the set, and we add the current element to the set. For example, if the elements in a set: [1,3,4,6], the current element is 8, and if 8 is added to the set, it will form a longer set [1,3,4,6,8]. If the current element is smaller than the last element of the collection, we can have the current element replace the first element in the collection that is larger than it in order to keep the elements in the collection as small as possible. For example, if the elements in the set: [1,3,5,6] and the current element is 4, we can replace 4 with 5 to become [1,3,4,6], because the smaller the elements in the set, the greater the chance of forming the longest increasing subsequence. Because the elements in the collection are all ordered, substitutions only require a binary lookup. JAVA: public int lengthOfLIS(int[] nums) { // mList is the composition of the ascending subsequence List mList = new ArrayList<>(nums.length); } for (int num : nums) { // Add to the last if (mList.size() == 0 || mList.get(mList.size() - 1) < num) mList.add(num); } else { // binary search int i = Collections.binarySearch(mList, num); } } Replace, note here that if found, i will return the subscript of the found element, if it is not found // it will return the location where it should be stored, and then take the negation, so it is a negative number. mList.set((i < 0) ? -i - 1 : i, num); } } return mList.size(); } C++： public: int lengthOfLIS(vector &nums) { vector mList; mList.reserve(nums.size()); for (int num: nums) { if (mList.empty() || mList.back() < num) { mList.push_back(num); } else { // binary lookup auto it = lower_bound(mList.begin(), mList.end(), num); } *it = num; } } return mList.size(); } Python: def lengthOfLIS(self, nums: List[int]) -> int: mList = [] for num in nums: if not mList or mList[-1] < num: mList.append(num) else: # Binary lookup i = bisect_left(mList, num) mList[i] = num return len(mList) About the author Bo Ge, real name: Wang Yibo, graduated for more than ten years, author of "Algorithm Cheats", focusing on data structures and algorithms Download more than 1000 pages of PDF algorithm documents that I have collated. "Conquering Data Structures" column Arrays, Sparse Tables, Unidirectional Linked Lists, Bidirectional Linked Lists, Blocked Linked Lists, Jump Tables, Queues and Circular Queues, Double-Ended Queues, Monotonic Queues, Stacks, Monotonic Stacks, Double-Ended Stacks, Hash Tables, Heaps, Trie Trees, ArrayMap, SparseArray, Binary Trees, BST, Cartesian Tree, AVL Tree, Treap, FHQ-Treap ...... Classical Graph Theory Algorithm Column Introduction of graphs, representation of graphs, adjacency matrix transformation, breadth-first search (BFS), depth-first search (DFS), A* search algorithm, Iterative deepening depth-first search (IDDFS), IDA* algorithm, two-way breadth-first search, Dijkstra algorithm, Bellman-Ford algorithm, SPFA algorithm, Floyd algorithm ......