给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。c语言代码
时间: 2024-03-23 16:40:28 浏览: 18
好的,以下是使用动态规划算法实现的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`数组中的最大值即为所求的最长递增子序列长度。
希望这个代码能够帮到你!