题目:给定一个整数数组找到该数组中长度最长的连续递增子序列的长度并输出该长度。请用算法进行设计并求出时间复杂度。用c语言实现
算法设计:
- 定义变量max_len和curr_len,分别表示当前最长连续递增子序列的长度和当前连续递增子序列的长度。
- 遍历整个数组,从第二个元素开始比较当前元素和前一个元素的大小关系: a. 如果当前元素大于前一个元素,则curr_len加1。 b. 否则,更新max_len和curr_len的值,使得max_len为当前连续递增子序列的长度,curr_len重新计数为1。
- 返回max_len的值。
时间复杂度:O(n),其中n为数组的长度。
C语言实现:
#include <stdio.h>
int findLengthOfLCIS(int* nums, int numsSize){
if (numsSize <= 0) {
return 0;
}
int max_len = 1, curr_len = 1;
for (int i = 1; i < numsSize; i++) {
if (nums[i] > nums[i-1]) {
curr_len++;
} else {
max_len = curr_len > max_len ? curr_len : max_len;
curr_len = 1;
}
}
return max_len > curr_len ? max_len : curr_len;
}
int main() {
int nums[] = {1,3,5,4,7,8,9,10,11};
int numsSize = sizeof(nums) / sizeof(int);
int res = findLengthOfLCIS(nums, numsSize);
printf("Length of longest continuous increasing subsequence: %d\n", res);
return 0;
}
``
原文地址: https://www.cveoy.top/t/topic/hftK 著作权归作者所有。请勿转载和采集!