【数据结构】最长连续递增子序列

题目链接

习题3.4 最长连续递增子序列 - 浙大版《数据结构（第2版）》题目集

整体思路

使用三个数组list、maxSeqList、tempList。

List存储输入的元素；

maxSeqList存储到目前位置最长的子序列；

tempList存储当前的子序列

遍历List，将当前的子序列存储到tempList并用cnt计数。即如果后一个元素大于当前元素，认为是递增子序列，当前元素存入tempList，cnt自增；如果后一个元素小于或等于当前元素，认为不是递增子序列。此时当前元素应为tempList最后一个元素，将当前元素存入tempList，再将cnt与maxSeqCnt比较来决定是否更新maxSeqList。最后计数器清零，准备读入下一个子序列

代码

#include <stdio.h>
#include <stdlib.h>int main()
{int n;int *list;          // 顺序存储输入整数int *maxSeqList;    // 存储最长连续递增子序列int *tempList;      // 存储临时递增子序列int cnt = 0;        // 子序列计数int maxCnt = 0;     // 最大子序列计数// 输入正整数nscanf("%d\n", &n);// 分配内存空间list = (int *)malloc(sizeof(n) * n);maxSeqList = (int *)malloc(sizeof(n) * n);tempList = (int *)malloc(sizeof(n) * n);// 将输入整数存入list数组for (int i = 0; i < n; i++){scanf("%d", &list[i]);}// 遍历list数组for (int i = 0; i < n; i++){if (list[i] < list[i+1]){// 如果后一个元素大于当前元素，递增，当前元素存入tempListtempList[cnt] = list[i];cnt++;}else{// 如果后一个元素小于或等于当前元素，不递增。此时也将当前元素存入tempList，原因是if判断为真时未将后一个元素存入tempListtempList[cnt] = list[i];cnt++;if (cnt > maxCnt){// 如果当前子序列的长度大于最长子序列，将当前子序列tempList赋值给最长子序列maxSeqListmaxCnt = cnt;for (int j = 0; j < maxCnt; j++){maxSeqList[j] = tempList[j];}}// 当前子序列计数清零cnt = 0;}}// 将最长子序列输出，结尾不输出空格for (int i = 0; i < maxCnt; i++){if (i == maxCnt - 1){printf("%d", maxSeqList[i]);}else{printf("%d ", maxSeqList[i]);}}// 释放申请内存free(list);free(maxSeqList);free(tempList);return 0;
}