给你一个整数数组 nums，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如 [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列，用c语言实现

哈喽！欢迎和我聊天~ 很高兴能回答你的问题。

关于你的问题，我可以给你一个动态规划的解法。假设dp[i]表示以nums[i]作为结尾的最长递增子序列长度，那么我们可以通过逐一比较nums[i]和nums[0]~nums[i-1]的大小来推导出dp[i]的值。具体地，我们有以下递推式:

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

也就是说，dp[i]的值等于所有满足nums[j] < nums[i]的dp[j]的最大值加1。最终答案就是dp数组中的最大值。

代码实现如下：

int lengthOfLIS(int* nums, int numsSize){
    int dp[numsSize], res = 0;
    for(int i = 0; i < numsSize; i++) {
        int max_len = 0;
        for(int j = 0; j < i; j++) {
            if(nums[j] < nums[i]) {
                max_len = fmax(max_len, dp[j]);
            }
        }
        dp[i] = max_len + 1;
        res = fmax(res, dp[i]);
    }
    return res;
}

希望这个回答能够解决你的问题。如果你还有其他的问题，欢迎继续和我聊天哦~

相关问题

c++给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

这是一个经典的动态规划问题，可以使用 O(n^2) 或者 O(nlogn) 的算法解决。

O(n^2) 的算法思路是定义一个 dp 数组，其中 dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。初始化 dp 数组为 1，即每个元素本身就是一个长度为 1 的严格递增子序列。然后从前往后遍历数组，对于每个位置 i，枚举其前面的所有位置 j，如果 nums[j] < nums[i]，则更新 dp[i] = max(dp[i], dp[j] + 1)。

O(nlogn) 的算法思路是使用贪心+二分查找的方法。定义一个 tails 数组，其中 tails[i] 表示长度为 i+1 的严格递增子序列的最后一个元素的最小值。初始化 tails 数组为一个只包含 nums[0] 的数组。然后从第二个元素开始遍历数组，对于每个元素 nums[i]，如果 nums[i] > tails[len-1]，则将 nums[i] 添加到 tails 数组的末尾，长度加 1；否则在 tails 数组中二分查找第一个大于等于 nums[i] 的位置 j，将 tails[j] 替换为 nums[i]。最终 tails 数组的长度就是最长严格递增子序列的长度。

以下是 O(n^2) 的 C++ 代码实现：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

以下是 O(nlogn) 的 C++ 代码实现：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> tails;
    tails.push_back(nums[0]);
    for (int i = 1; i < n; i++) {
        if (nums[i] > tails.back()) {
            tails.push_back(nums[i]);
        } else {
            int left = 0, right = tails.size() - 1;
            while (left < right) {
                int mid = (left + right) / 2;
                if (tails[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = nums[i];
        }
    }
    return tails.size();
}

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。c语言代码

好的，以下是使用动态规划算法实现的C语言代码：

#include <stdio.h>

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }

    int dp[numsSize];
    dp[0] = 1;
    int maxLen = 1;

    for (int i = 1; i < numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
            }
        }
        maxLen = maxLen > dp[i] ? maxLen : dp[i];
    }

    return maxLen;
}

int main() {
    int nums[] = {0, 3, 1, 6, 2, 2, 7};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int ans = lengthOfLIS(nums, numsSize);
    printf("%d\n", ans);
    return 0;
}

解释一下代码实现：

- 首先判断输入数组是否为空，如果是直接返回0；
- 定义一个长度为`numsSize`的`dp`数组，用来记录以当前数字为结尾的最长递增子序列长度；
- 初始化`dp[0]`为1，因为以第一个数字结尾的最长递增子序列长度为1；
- 对于每一个数字i，从0到i-1遍历数组，如果当前数字nums[i]大于nums[j]，说明可以将j加入以i结尾的最长递增子序列，此时`dp[i] = dp[j] + 1`；
- 遍历完所有数字后，`dp`数组中的最大值即为所求的最长递增子序列长度。

希望这个代码能够帮到你！