题目描述

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

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

示例：

• 输入：nums = [10,9,2,5,3,7,101,18]

• 输出：4

• 解释：最长递增子序列是 [2,3,7,18]，因此长度为 4。

核心思路（动态规划）

这道题是典型的动态规划入门题，核心是用 dp 数组记录状态，再通过状态转移方程递推求解。

1. 定义状态

dp[i] 表示：以 nums[i] 为结尾的最长严格递增子序列的长度。

2. 初始化

每个元素本身就是一个长度为 1 的递增子序列，所以 dp 数组的初始值全部为 1。

3. 状态转移

对于每个位置 i（从 1 开始遍历），检查它之前的所有位置 j（j < i）：

• 如果 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面，形成更长的序列。

• 此时更新状态：dp[i] = max(dp[i], dp[j] + 1)

4. 结果计算

遍历完成后，dp 数组中的最大值，就是整个数组的最长递增子序列长度。

Java代码实现

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 边界处理：数组为空时直接返回0
        if (nums.length == 0) {
            return 0;
        }

        // 1. 初始化dp数组，每个元素初始值为1
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        // 2. 状态转移：双重循环计算每个位置的dp值
        for (int i = 1; i < nums.length; i++) {
            // 检查i之前的所有位置j
            for (int j = 0; j < i; j++) {
                // 如果nums[j] < nums[i]，则可以更新dp[i]
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 3. 找到dp数组中的最大值，即为答案
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }

        return maxLength;
    }
}