给定一个数组 nums，找到其中最长严格上升子序列的长度。 示例: 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长的上升子序列是 [2,3,7,101]，它的长度是 4。

这是一道经典的动态规划问题，可以用 O(n^2) 的时间复杂度解决。具体来说，我们可以定义一个 dp 数组，其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。初始时，dp 数组中的所有元素都为 1，因为每个元素都可以看作是一个长度为 1 的上升子序列。

然后我们枚举 j∈[0,i)，如果 nums[j]<nums[i]，那么 nums[i] 可以接在 nums[j] 后面形成一个更长的上升子序列，因此 dp[i]=max(dp[i],dp[j]+1)。最终的结果即为 dp 数组中的最大值。

以下是 Python 代码实现：

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

对于输入样例 [10,9,2,5,3,7,101,18]，该函数的输出为 4。

相关问题

/** 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例1：输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的 **/

这个问题是关于数组求交集的，可以使用哈希表来实现。先遍历其中一个数组，将其中的元素添加到哈希表中。然后再遍历另一个数组，如果哈希表中存在相同的元素，则加入结果集合中。Java代码实现如下：

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    Set<Integer> intersect = new HashSet<>();
    for (int num : nums1) {
        set.add(num);
    }
    for (int num : nums2) {
        if (set.contains(num)) {
            intersect.add(num);
        }
    }
    int[] result = new int[intersect.size()];
    int index = 0;
    for (int num : intersect) {
        result[index++] = num;
    }
    return result;
}

使用kotlin完成这个题目：349. 两个数组的交集 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2： 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的 提示： 1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000

以下是使用 Kotlin 实现求两个数组的交集的代码：

fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
    val set1 = nums1.toSet()
    val set2 = nums2.toSet()
    return (set1 intersect set2).toIntArray()
}

这段代码中，我们首先将 `nums1` 和 `nums2` 转换为 `Set` 集合，然后使用 `intersect` 函数求两个集合的交集。最后，将交集转换为数组并返回即可。

这样，我们就完成了求两个数组的交集的实现。在上述示例中，我们可以调用 `intersection(intArrayOf(1, 2, 2, 1), intArrayOf(2, 2))`，得到 `[2]`。再调用 `intersection(intArrayOf(4, 9, 5), intArrayOf(9, 4, 9, 8, 4))`，得到 `[9, 4]`。