最长递增子序列（Longest Increasing Subsequence，简称 LIS）

最长递增子序列（Longest Increasing Subsequence，简称 LIS）问题是一个经典的动态规划问题。给定一个序列，找出其中最长的递增子序列，返回该子序列的长度。

例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，其中最长递增子序列是 [2, 3, 7, 101]，因此返回值为 4。

解法：

一般来说，动态规划问题都有以下三个要素：

1.状态定义：定义状态，明确状态含义。

对于 LIS 问题，我们可以定义状态 dp[i] 表示以第 i 个数为结尾的最长递增子序列的长度。

2.状态转移：根据状态定义，设计状态转移方程。

对于状态 dp[i]，需要在 [0, i) 的范围内找到一个数 j，使得 nums[j] < nums[i]，并且 dp[j] 的值最大。因此，状态转移方程为：

dp[i] = max(dp[j]) + 1, 0 ≤ j < i，nums[j] < nums[i]

3.初始状态：根据状态定义，确定初始状态。

对于 LIS 问题，初始状态为 dp[i] = 1，即任意一个单独的数都可以构成一个长度为 1 的递增子序列。

最终的结果是所有状态 dp[i] 中的最大值。

具体实现代码如下：

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1); // 初始化为 1

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

其中，dp 数组表示以每个位置为结尾的最长递增子序列长度。初始时，所有位置的最长递增子序列长度都是 1，因为任何一个数都可以单独成为一个递增子序列。

然后，对于每个位置 i，我们需要在 [0, i) 的范围内找到一个数 j，使得 nums[j] < nums[i]，并且 dp[j] 的值最大。此时，dp[i] 的值就是 dp[j] 的值加上 1，即以 nums[i] 结尾的最长递增子序列的长度。

最后，遍历 dp 数组，找到其中的最大值，即为最终结果。

时间复杂度为 O(n^2)，其中 n 为数组的长度。