写一段判断最长上升子序列的代码

以下是一段 Python 代码，用于判断最长上升子序列：

def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

该代码使用动态规划的思想，dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。初始值为 1，因为每个元素本身也可以作为一个上升子序列。然后，我们遍历每个元素，对于每个元素，我们再遍历它之前的所有元素，如果发现前面有元素小于当前元素，那么以前面元素为结尾的最长上升子序列可以和当前元素构成一个更长的上升子序列，因此我们更新 dp[i] 的值。最终，dp 数组中的最大值就是最长上升子序列的长度。

相关问题

最长公共上升子序列代码

以下是最长公共上升子序列的代码实现（使用动态规划）：

def LCS(arr1, arr2):
    m, n = len(arr1), len(arr2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if arr1[i-1] == arr2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

其中，`arr1`和`arr2`分别是两个需要比较的序列，`m`和`n`分别是它们的长度。`dp`是一个二维数组，表示最长公共上升子序列的长度。在每次遍历中，如果当前两个元素相等，则最长公共上升子序列长度加1；否则，取左边和上边的最大值作为当前最长公共上升子序列的长度。最后返回`dp[m][n]`即可。

最长上升子序列贪心 java代码

以下是最长上升子序列的贪心算法的Java代码：

public static int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int res = 0;
    for (int num : nums) {
        int i = 0, j = res;
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (tails[mid] < num) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        tails[i] = num;
        if (res == j) res++;
    }
    return res;
}

算法思路：

1. 创建一个长度为 nums.length 的数组 tails，tails[i] 表示长度为 i 的上升子序列的末尾元素的最小值。
2. 遍历 nums 数组，对于每个元素 num，将其二分插入 tails 数组中。
3. 如果 num 大于 tails 数组的最后一个元素，那么将 num 放到 tails 数组的末尾。
4. 如果 num 在 tails 数组中的位置 i 大于 0，那么 tails[i-1] < num < tails[i]，则用 num 替换 tails[i]，使得 tails 数组中的元素依旧保持上升的顺序。
5. 如果 num 在 tails 数组中的位置 i 等于 0，那么 tails[i-1] 不存在，num 就是新的最小值，将其放到 tails 数组的开头。
6. 最终 tails 数组的长度就是最长上升子序列的长度。

时间复杂度：O(nlogn)，其中 n 是 nums 数组的长度。tails 数组的长度不超过 n，因此外层循环的时间复杂度是 O(n)，内层循环的时间复杂度是 O(logn)。总时间复杂度为 O(nlogn)。