一维数组：最长上升子序列

1. 问题描述和示例

问题描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,18]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
解释：最长递增子序列是 [0,1,2,3]，因此长度为 4 。

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1
解释：最长递增子序列是 [7]，因此长度为 1 。

约束条件：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

2. 核心难点分析

主要难点

1. 状态定义：如何定义动态规划的状态
2. 状态转移：如何从前面的状态推导出当前状态
3. 时间优化：如何从O(n²)优化到O(nlogn)
4. 二分查找：在优化解法中如何正确使用二分查找

关键要点

• 子序列不要求连续，但要求保持原有顺序
• 严格递增意味着不能有相等的元素
• 需要找的是长度，不是具体的子序列
• 可以用动态规划或贪心+二分查找解决

3. 多种解法对比

解法一：动态规划（基础版）

• 思路：dp[i]表示以nums[i]结尾的最长递增子序列长度
• 优点：思路清晰，容易理解
• 缺点：时间复杂度O(n²)

解法二：贪心 + 二分查找（优化版）

• 思路：维护一个递增数组，用二分查找优化插入位置
• 优点：时间复杂度O(nlogn)，最优解
• 缺点：理解难度较大

解法三：动态规划 + 二分查找

• 思路：结合DP思想和二分查找优化
• 优点：兼顾理解和效率
• 缺点：实现相对复杂

4. 详细Java代码实现

解法一：动态规划（O(n²)）

public class Solution {
    /**
     * 使用动态规划求最长递增子序列长度
     * @param nums 输入数组
     * @return 最长递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
        int[] dp = new int[n];
        
        // 初始化：每个元素自身构成长度为1的递增子序列
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        
        // 状态转移
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 如果 nums[i] > nums[j]，可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        // 找到所有dp[i]中的最大值
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        
        return maxLength;
    }
}

解法一的优化版本（记录具体序列）

public 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[] prev = new int[n]; // 记录前驱节点，用于重构序列
        
        // 初始化
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            prev[i] = -1; // -1表示没有前驱
        }
        
        int maxLength = 1;
        int maxIndex = 0;
        
        // 动态规划
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j; // 记录前驱
                }
            }
            
            // 更新最大长度和对应索引
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                maxIndex = i;
            }
        }
        
        // 重构最长递增子序列（可选）
        reconstructLIS(nums, prev, maxIndex);
        
        return maxLength;
    }
    
    /**
     * 重构最长递增子序列
     */
    private void reconstructLIS(int[] nums, int[] prev, int maxIndex) {
        List<Integer> lis = new ArrayList<>();
        int current = maxIndex;
        
        while (current != -1) {
            lis.add(nums[current]);
            current = prev[current];
        }
        
        Collections.reverse(lis);
        System.out.println("最长递增子序列: " + lis);
    }
}

解法二：贪心 + 二分查找（O(nlogn)）

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

public class Solution {
    /**
     * 使用贪心算法 + 二分查找求最长递增子序列长度
     * @param nums 输入数组
     * @return 最长递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // tails[i] 表示长度为 i+1 的递增子序列的最小尾部元素
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            // 使用二分查找找到 num 应该插入的位置
            int pos = binarySearch(tails, num);
            
            if (pos == tails.size()) {
                // num 比所有尾部元素都大，直接添加
                tails.add(num);
            } else {
                // 替换位置 pos 的元素，保持 tails 数组的最优性
                tails.set(pos, num);
            }
        }
        
        return tails.size();
    }
    
    /**
     * 二分查找：找到第一个大于等于 target 的位置
     * @param tails 有序数组
     * @param target 目标值
     * @return 插入位置
     */
    private int binarySearch(List<Integer> tails, int target) {
        int left = 0, right = tails.size();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (tails.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

解法二的数组版本

public 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 pos = binarySearch(tails, 0, size, num);
            
            tails[pos] = num;
            
            if (pos == size) {
                size++;
            }
        }
        
        return size;
    }
    
    /**
     * 在数组中进行二分查找
     */
    private int binarySearch(int[] tails, int left, int right, int target) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (tails[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

解法三：使用Java内置二分查找

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

public class Solution {
    /**
     * 使用Collections.binarySearch简化实现
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            int pos = Collections.binarySearch(tails, num);
            
            if (pos < 0) {
                // binarySearch返回负数表示未找到，转换为插入位置
                pos = -(pos + 1);
            }
            
            if (pos == tails.size()) {
                tails.add(num);
            } else {
                tails.set(pos, num);
            }
        }
        
        return tails.size();
    }
}

5. 测试用例和预期结果

测试用例

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：[10,9,2,5,3,7,101,18]
        int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("测试用例1结果: " + solution.lengthOfLIS(nums1)); 
        // 预期输出：4 (子序列: [2,3,7,18] 或 [2,3,7,101])
        
        // 测试用例2：[0,1,0,3,2,3]
        int[] nums2 = {0, 1, 0, 3, 2, 3};
        System.out.println("测试用例2结果: " + solution.lengthOfLIS(nums2)); 
        // 预期输出：4 (子序列: [0,1,2,3])
        
        // 测试用例3：[7,7,7,7,7,7,7]
        int[] nums3 = {7, 7, 7, 7, 7, 7, 7};
        System.out.println("测试用例3结果: " + solution.lengthOfLIS(nums3)); 
        // 预期输出：1 (子序列: [7])
        
        // 测试用例4：单调递增数组
        int[] nums4 = {1, 2, 3, 4, 5};
        System.out.println("测试用例4结果: " + solution.lengthOfLIS(nums4)); 
        // 预期输出：5 (整个数组)
        
        // 测试用例5：单调递减数组
        int[] nums5 = {5, 4, 3, 2, 1};
        System.out.println("测试用例5结果: " + solution.lengthOfLIS(nums5)); 
        // 预期输出：1 (任意单个元素)
        
        // 测试用例6：空数组
        int[] nums6 = {};
        System.out.println("测试用例6结果: " + solution.lengthOfLIS(nums6)); 
        // 预期输出：0
        
        // 测试用例7：单个元素
        int[] nums7 = {1};
        System.out.println("测试用例7结果: " + solution.lengthOfLIS(nums7)); 
        // 预期输出：1
        
        // 测试用例8：包含负数
        int[] nums8 = {-10, -3, 0, 5, 9};
        System.out.println("测试用例8结果: " + solution.lengthOfLIS(nums8)); 
        // 预期输出：5 (整个数组)
        
        // 测试用例9：复杂情况
        int[] nums9 = {4, 10, 4, 3, 8, 9};
        System.out.println("测试用例9结果: " + solution.lengthOfLIS(nums9)); 
        // 预期输出：3 (子序列: [4,8,9] 或 [3,8,9])
    }
}

6. 边界情况处理

关键边界情况

1. 空数组：nums为null或长度为0
2. 单个元素：数组只有一个元素
3. 全部相同：所有元素都相同
4. 严格递增：数组本身就是递增的
5. 严格递减：数组是递减的
6. 包含负数：数组包含负数

边界处理技巧

// 统一的边界检查
if (nums == null || nums.length == 0) {
    return 0;
}

// 单个元素的特殊处理
if (nums.length == 1) {
    return 1;
}

// 在二分查找中正确处理边界
while (left < right) {
    int mid = left + (right - left) / 2; // 避免溢出
    if (tails.get(mid) < target) {
        left = mid + 1;
    } else {
        right = mid;
    }
}

7. 相关题目

类似题目

1. 354. 俄罗斯套娃信封问题：二维LIS问题
2. 673. 最长递增子序列的个数：求LIS的数量
3. 646. 最长数对链：变种的LIS问题
4. 435. 无重叠区间：贪心算法的应用
5. 452. 用最少数量的箭引爆气球：区间调度问题

扩展变种

1. 最长递减子序列：将比较条件改为 >
2. 最长非递减子序列：允许相等元素
3. 最长公共子序列：两个序列的LCS问题
4. 最长回文子序列：回文相关的DP问题

8. 复杂度分析

时间复杂度

• 动态规划法：O(n²)
  • 外层循环：O(n)
  • 内层循环：O(n)
  • 总体：O(n²)
• 贪心+二分查找：O(nlogn)
  • 外层循环：O(n)
  • 二分查找：O(logn)
  • 总体：O(nlogn)

空间复杂度

• 动态规划法：O(n)，需要dp数组
• 贪心+二分查找：O(n)，需要tails数组
• 两种方法的空间复杂度相同

最优解选择

推荐使用贪心+二分查找，因为：

• 时间复杂度更优：O(nlogn) vs O(n²)
• 空间复杂度相同：O(n)
• 在大数据量时性能优势明显
• 是面试中的期望解法

9. 面试要点总结

核心考点

1. 动态规划思维：状态定义和状态转移
2. 贪心算法：如何证明贪心策略的正确性
3. 二分查找：在有序数组中的应用
4. 算法优化：从O(n²)到O(nlogn)的优化思路

面试回答要点

1. 问题分析：这是一个经典的动态规划问题
2. 方法对比：先说DP解法，再提出优化方案
3. 算法原理：解释贪心策略为什么正确
4. 代码实现：写出清晰的代码
5. 复杂度分析：对比不同方法的复杂度

常见面试问题

• 能否优化到O(nlogn)？
• 如何输出具体的最长递增子序列？
• 如果要求非严格递增怎么办？
• 这个算法的实际应用场景是什么？

10. 性能优化技巧

贪心算法的核心思想

维护一个数组tails，其中tails[i]表示长度为i+1的递增子序列的最小尾部元素

关键性质：
1. tails数组始终保持递增
2. 对于相同长度的递增子序列，尾部元素越小越好
3. 这样可以为后续元素提供更多的选择空间

二分查找的优化

// 标准的lower_bound实现
private int lowerBound(int[] arr, int target, int size) {
    int left = 0, right = size;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

内存优化技巧

// 使用原地算法，复用输入数组空间
public int lengthOfLIS(int[] nums) {
    if (nums.length <= 1) {
        return nums.length;
    }
    
    int size = 0;
    
    for (int num : nums) {
        int pos = binarySearch(nums, 0, size, num);
        nums[pos] = num;
        
        if (pos == size) {
            size++;
        }
    }
    
    return size;
}

性能对比表

算法	时间复杂度	空间复杂度	实现难度	推荐度
动态规划	O(n²)	O(n)	简单	⭐⭐⭐
贪心+二分	O(nlogn)	O(n)	中等	⭐⭐⭐⭐⭐
记录路径的DP	O(n²)	O(n)	中等	⭐⭐⭐⭐

实际应用场景

1. 版本控制系统：找到最长的兼容版本序列
2. 股票交易：找到最长的上涨趋势
3. 生物信息学：DNA序列分析
4. 调度算法：任务调度的优化
5. 数据压缩：找到最优的压缩序列

总结

最长上升子序列是动态规划的经典问题，核心在于：

1. 理解DP状态的定义和转移
2. 掌握贪心+二分查找的优化思路
3. 熟练使用二分查找算法
4. 理解算法优化的思维过程

这道题展现了从暴力解法到优化解法的完整思维过程，是算法面试中的高频题目。建议先掌握DP解法，再深入理解贪心优化，最后练习相关的变种问题。