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

以下是一段 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 数组中的最大值就是最长上升子序列的长度。

相关问题

用c语言写一个判断最长上升子序列的函数

在C语言中，可以使用动态规划的方法编写一个用于计算给定整数数组最长上升子序列长度的函数。下面是一个基本的实现，它使用了二维数组`dp`来存储每个元素到当前位置为止的最大上升子序列长度：

#include <stdio.h>

int lengthOfLIS(int arr[], int n) {
    if (n == 0) return 0;
    int dp[n];
    dp[0] = 1; // 初始化第一个元素的子序列长度为1

    for (int i = 1; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    return *max_element(dp, dp + n); // 找到并返回最大值
}

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Length of longest increasing subsequence: %d\n", lengthOfLIS(arr, n));
    return 0;
}

这个函数首先初始化一个大小为`n`的一维数组`dp`，其中`dp[i]`表示以`arr[i]`结尾的最长上升子序列长度。然后遍历数组，对于每个元素，检查之前的所有元素是否能形成更长的上升子序列，并更新`dp[i]`。最后，通过`max_element`找到并返回`dp`数组中的最大值，即为最长上升子序列的长度。

最长上升子序列的代码

最长上升子序列是一个经典的计算机科学问题，通常通过动态规划来解决。下面是一个简单的Python代码示例，用于找到给定整数数组中最长的上升子序列：

def longest_increasing_subsequence(nums):
    if not nums: return []
    
    # 初始化一个长度为n+1的列表，所有元素初始值都设为1（表示至少有一个元素）
    dp = [1] * len(nums)
    
    for i in range(len(nums)):
        for j in range(i):
            # 如果当前元素小于前一个元素，并且dp[j]+1大于dp[i]，说明找到了更长的上升子序列
            if nums[i] > nums[j] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                
    # 找到最大值并返回对应的索引，即最长上升子序列的长度
    max_length = max(dp)
    index = dp.index(max_length)
    # 从nums中反向回溯构建最长上升子序列
    lis = [nums[index]]
    while index != 0:
        index -= 1
        if nums[index] < lis[-1] and dp[index] == dp[index - 1] + 1:
            lis.append(nums[index])
    return lis[::-1]  # 返回最长上升子序列

# 使用示例
numbers = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(numbers))  # 输出：[10, 2, 3, 7, 101]