最长递增子序列

描述

给你一个整数数组 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,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题的解题思路是使用动态规划（Dynamic Programming）。

首先，我们定义一个数组dp，其中dp[i]表示以nums[i]为结尾的最长递增子序列的长度。初始时，每个元素本身也可以看做一个长度为1的递增子序列，所以dp数组的初始值都为1。

接下来，我们遍历整个数组，对于每个元素nums[i]，我们再遍历它之前的所有元素nums[j]，如果nums[j]小于nums[i]，说明nums[i]可以接在nums[j]的后面，形成一个更长的递增子序列。此时，我们就可以更新dp[i]的值，即dp[i] = max(dp[i], dp[j] + 1)，其中dp[j] + 1表示在以nums[j]为结尾的最长递增子序列后面加上nums[i]，得到一个新的递增子序列，而dp[i]则表示当前以nums[i]为结尾的最长递增子序列的长度，我们取它们的较大值即可。

最后，我们遍历整个dp数组，取其中的最大值，即为原数组的最长递增子序列的长度。

这个算法的时间复杂度为$O(n^2)$，因为要遍历数组并计算每个元素的最长递增子序列长度。

C++代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0; // 如果数组为空，则最长递增子序列长度为0

        vector<int> dp(n, 1); // dp[i]表示以nums[i]为结尾的最长递增子序列长度
        int res = 1; // 最长递增子序列长度至少为1

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1); // 如果nums[i]比nums[j]大，则更新dp[i]
                }
            }
            res = max(res, dp[i]); // 更新最长递增子序列长度
        }

        return res;
    }
};