PTA最长连续递增子序列（链表实现，O（1））

题目链接

链表实现最长连续递增子序列，复杂度为O（1）

#include <stdio.h> #include <iostream> using namespace std; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LinkNode; int main() { int n; //输入操作start cin >> n; LinkNode *L, *pre, *s; L = (LinkNode *)malloc(sizeof(LinkNode)); L -> next = NULL; pre = L; for(int i = 0; i < n; i++) { ElemType x; cin >> x; s = (LinkNode *)malloc(sizeof(LinkNode)); s -> data = x; s -> next = pre -> next; pre -> next = s; pre = s; } //输入操作end int length = 1, Max_length = 1; LinkNode *start, *Max_start; pre = L -> next; start = L -> next; Max_start = start; while(pre != NULL) //遍历整个序列链表，两个whlie循环，复杂度为O(1) { length = 1; while((pre -> next != NULL) && (pre -> data < pre -> next -> data)) { length ++; pre = pre -> next; } if(length > Max_length) //记录最长子序列的开始位置 { Max_length = length; Max_start = start; } start = pre -> next; pre = pre -> next; } length = 1; //输出操作start cout<< Max_start -> data; Max_start = Max_start -> next; while(Max_start != NULL && length < Max_length) { cout << ' '<< Max_start -> data ; Max_start = Max_start -> next; length ++; } //输出操作end return 0; }