1. 📌 Problem Links

• LeetCode 300: Longest Increasing Subsequence

2. 🧠 Solution Overview

This problem requires finding the length of the longest subsequence in an array where elements are in strictly increasing order. A subsequence is derived from the original array by deleting some elements without changing the order of the remaining elements . Below are the main approaches:

Method	Key Idea	Time Complexity	Space Complexity
Dynamic Programming	DP array storing LIS ending at each position	O(n²)	O(n)
Binary Search Optimization	Maintain potential subsequences with binary search	O(n log n)	O(n)
Patience Sorting	Greedy approach with piles simulation	O(n log n)	O(n)

3. 🟢 Solution 1: Dynamic Programming (Bottom-Up)

3.1. Algorithm Idea

We use a DP array where dp[i] represents the length of the longest increasing subsequence ending at position i. The key insight is that each dp[i] can be computed by checking all previous positions j < i - if nums[i] > nums[j], we can extend the subsequence ending at j to include i .

3.2. Key Points

• State Definition: dp[i] = length of LIS ending at index i
• State Transition: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
• Initialization: All dp[i] = 1 (each element is a subsequence of length 1)
• Final Answer: max(dp[0...n-1])
• Processing Order: Process elements left to right

3.3. Java Implementation

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int n = nums.length;
        int[] dp = new int[n];
        int maxLength = 1;
        
        for (int i = 0; i < n; i++) {
            dp[i] = 1;  // Each element is at least a subsequence of length 1
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
}

3.4. Complexity Analysis

• Time Complexity: O(n²) - Nested loops over all elements
• Space Complexity: O(n) - DP array of size n

4. 🟡 Solution 2: Binary Search Optimization

4.1. Algorithm Idea

This approach maintains an array tails where tails[i] stores the smallest possible tail value for all increasing subsequences of length i+1. As we process each number, we use binary search to find its position in the tails array - either extending an existing subsequence or potentially creating a new one .

4.2. Key Points

• Array Maintenance: tails array keeps smallest tail values
• Binary Search: For each number, find where it fits in tails
• Two Cases:
  • If number > all tails, append it (increases LIS length)
  • Else, replace first tail that’s ≥ current number
• Result: Length of tails array is the answer

4.3. Java Implementation

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int[] tails = new int[nums.length];
        int size = 0;
        
        for (int num : nums) {
            int left = 0, right = size;
            
            // Binary search to find position
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            tails[left] = num;
            if (left == size) {
                size++;
            }
        }
        
        return size;
    }
}

4.4. Complexity Analysis

• Time Complexity: O(n log n) - Single pass with binary search per element
• Space Complexity: O(n) - tails array of size n

5. 🔵 Solution 3: Patience Sorting Approach

5.1. Algorithm Idea

This approach simulates a patience card game where we maintain multiple “piles” of cards. Each new number either starts a new pile or is placed on the leftmost pile whose top card is greater than or equal to the current number. The number of piles at the end gives the LIS length .

5.2. Key Points

• Pile Management: Maintain piles where each pile is decreasing
• Greedy Placement: Always place card on leftmost valid pile
• TreeSet Alternative: Can use Java’s TreeSet with ceiling operations
• Result Interpretation: Number of piles = LIS length

5.3. Java Implementation

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // TreeSet version - more intuitive but similar performance
        ArrayList<Integer> piles = new ArrayList<>();
        
        for (int num : nums) {
            int left = 0, right = piles.size();
            
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (piles.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            if (left == piles.size()) {
                piles.add(num);
            } else {
                piles.set(left, num);
            }
        }
        
        return piles.size();
    }
}

5.4. Complexity Analysis

• Time Complexity: O(n log n) - Same as binary search approach
• Space Complexity: O(n) - For storing piles

6. 📊 Solution Comparison

Solution	Time	Space	Pros	Cons
Standard DP	O(n²)	O(n)	Intuitive, easy to implement	Too slow for large n
Binary Search	O(n log n)	O(n)	Optimal time complexity	Less intuitive
Patience Sorting	O(n log n)	O(n)	Conceptual elegance	Same complexity as binary search

7. 💡 Summary

For the Longest Increasing Subsequence problem:

• Learning & Understanding: Start with Standard DP to grasp the fundamental state transition concept
• Interviews & Practical Use: Binary Search Optimization offers optimal O(n log n) performance
• Mathematical Insight: The average LIS length in random permutations is approximately 2√n

The key insight is recognizing the optimal substructure - the LIS ending at each position can be built from LIS ending at previous positions .

The search for the longest increasing subsequence mirrors our own journey of growth - we build upon our past experiences, carefully selecting which paths to extend and which to replace, always striving for the most optimal progression toward our goals.

---

中文版本

1. 📌 题目链接

• 力扣 300: 最长递增子序列
• LeetCode 300: Longest Increasing Subsequence

2. 🧠 解法概览

这个问题要求找到数组中最长严格递增子序列的长度。子序列是通过从原始数组删除一些元素而不改变剩余元素顺序得到的序列 。主要解法如下：

方法	核心思想	时间复杂度	空间复杂度
动态规划	DP数组存储每个位置结尾的LIS	O(n²)	O(n)
二分查找优化	用二分查找维护潜在子序列	O(n log n)	O(n)
耐心排序	模拟堆牌游戏的贪心方法	O(n log n)	O(n)

3. 🟢 解法1：动态规划（自底向上）

3.1. 算法思路

我们使用一个DP数组，其中dp[i]表示以位置i结尾的最长递增子序列的长度。关键洞察是每个dp[i]可以通过检查所有前序位置j < i来计算 - 如果nums[i] > nums[j]，我们可以扩展以j结尾的子序列以包含i 。

3.2. 解法关键点

• 状态定义：dp[i] = 以索引i结尾的LIS长度
• 状态转移：dp[i] = max(dp[j] + 1) 对所有j < i且nums[j] < nums[i]
• 初始化：所有dp[i] = 1（每个元素本身是长度为1的子序列）
• 最终答案：max(dp[0...n-1])
• 处理顺序：从左到右处理元素

3.3. Java实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int n = nums.length;
        int[] dp = new int[n];
        int maxLength = 1;
        
        for (int i = 0; i < n; i++) {
            dp[i] = 1;  // 每个元素至少是长度为1的子序列
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
}

3.4. 时间空间复杂度

• 时间复杂度：O(n²) - 对所有元素的嵌套循环
• 空间复杂度：O(n) - 大小为n的DP数组

4. 🟡 解法2：二分查找优化

4.1. 算法思路

这种方法维护一个数组tails，其中tails[i]存储所有长度为i+1的递增子序列的最小可能尾值。当我们处理每个数字时，使用二分查找找到它在tails数组中的位置 - 要么扩展现有子序列，要么可能创建新子序列 。

4.2. 解法关键点

• 数组维护：tails数组保持最小的尾值
• 二分查找：对每个数字，找到在tails中的位置
• 两种情况：
  • 如果数字 > 所有尾值，追加它（增加LIS长度）
  • 否则，替换第一个 ≥ 当前数字的尾值
• 结果：tails数组的长度就是答案

4.3. Java实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int[] tails = new int[nums.length];
        int size = 0;
        
        for (int num : nums) {
            int left = 0, right = size;
            
            // 二分查找找到位置
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            tails[left] = num;
            if (left == size) {
                size++;
            }
        }
        
        return size;
    }
}

4.4. 时间空间复杂度

• 时间复杂度：O(n log n) - 单次遍历配合每个元素的二分查找
• 空间复杂度：O(n) - 大小为n的tails数组

5. 🔵 解法3：耐心排序方法

5.1. 算法思路

这种方法模拟耐心纸牌游戏，我们维护多个"牌堆"。每个新数字要么开始一个新牌堆，要么放在最左边的顶牌大于等于当前数字的牌堆上。最终的牌堆数量就是LIS长度 。

5.2. 解法关键点

• 牌堆管理：维护每个牌堆都是递减的
• 贪心放置：总是将牌放在最左边的有效牌堆上
• TreeSet替代：可以使用Java的TreeSet配合ceiling操作
• 结果解释：牌堆数量 = LIS长度

5.3. Java实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // TreeSet版本 - 更直观但性能相似
        ArrayList<Integer> piles = new ArrayList<>();
        
        for (int num : nums) {
            int left = 0, right = piles.size();
            
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (piles.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            if (left == piles.size()) {
                piles.add(num);
            } else {
                piles.set(left, num);
            }
        }
        
        return piles.size();
    }
}

5.4. 时间空间复杂度

• 时间复杂度：O(n log n) - 与二分查找方法相同
• 空间复杂度：O(n) - 用于存储牌堆

6. 📊 解法对比

解法	时间	空间	优点	缺点
标准DP	O(n²)	O(n)	直观，易于实现	对大n太慢
二分查找	O(n log n)	O(n)	最优时间复杂度	不太直观
耐心排序	O(n log n)	O(n)	概念优雅	与二分查找相同复杂度

7. 💡 总结

对于最长递增子序列问题：

• 学习与理解：从标准DP开始掌握基本状态转移概念
• 面试与实践：二分查找优化提供最优的O(n log n)性能
• 数学洞察：随机排列中平均LIS长度约为2√n

关键洞察是认识到最优子结构特性 - 每个位置结尾的LIS可以从前序位置结尾的LIS构建 。

寻找最长递增子序列的过程映照着我们自身的成长旅程 - 我们在过去经验的基础上构建，仔细选择扩展哪些路径、替换哪些路径，始终为达到目标寻求最优的发展进程。