HBU DS 1-9 最长连续递增子序列 (20分)
给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
输入格式:
输入第1行给出正整数n（≤105）；第2行给出n个整数，其间以空格分隔。
输出格式:
在一行中输出第一次出现的最长连续递增子序列，数字之间用空格分隔，序列结尾不能有多余空格。
输入样例：
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10
输出样例：
3 4 6 8
这个题用的在线算法。我觉得这个题的难点在于几个指针，如果不用输出序列只输出最大数的话，很简单。就是这个指针，刚写这个题那会我弄不太明白，然后上次写了一个题可能也是蒙对了。刚开始就是有几个点过不去，过了可能一个星期吧，我又重写了一下，先是用数据，一次提交就AC了。然后又换成链表，也一次提交就AC了。
思路：
一个left指针指向序列开始的地方（对于链表就是指向节点，对于数组就是索引），right指针指向最大序列的结束地方。我们必须存下最长序列的left和right，但同时，我们在进行循环时，得存下可能是最长序列的开始位置，需要一个temp指针。如果新的序列长于之前最长的序列，就把temp赋值给left，然后把当前的i赋值给right。数组的话，比较两个相邻的大小直接索引对应i和i-1 ，链表的话，需要一个pre指针。
代码_数组:
#include <iostream>
#define MAXN 100000
using namespace std;
struct Node
{
int data[MAXN];
int last;
};
int main()
{
Node L;
L.last = -1;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> L.data[i];
L.last++;
}
int maxNum = 0, currNum = 1;
int left = 0, right = 0, temp = 0; //temp left
for (int i = 1; i <= L.last; i++)
{
if (L.data[i - 1] < L.data[i])
{
currNum++;
if (currNum > maxNum)
{
maxNum = currNum;
left = temp;
right = i;
}
}
else
{
currNum = 1;
temp = i;
}
}
for (int i = left; i <= right; i++)
{
if (i != left)
cout << " ";
cout << L.data[i];
}
}
代码_链表：
#include <iostream>
using namespace std;
typedef struct Node *List;
struct Node
{
int data;
List next;
};
int main()
{
List L = (List)malloc(sizeof(Node)), tmp, s, pre;
L->next = NULL;
tmp = L;
int n;
cin >> n;
while (n--)
{
s = (List)malloc(sizeof(Node));
cin >> s->data;
s->next = NULL;
tmp->next = s;
tmp = s;
}
//输入进来了
tmp = L->next->next; //tmp从第二个开始
pre = L->next;
int currnum = 0, maxnum = 1;
List left = L->next, right = L->next, temp = L->next;
while (tmp)
{
if (tmp->data > pre->data)
{
currnum++;
if (currnum > maxnum)
{
maxnum = currnum;
left = temp;
right = tmp;
}
}
else
{
currnum = 1;
temp = tmp;
}
pre = tmp;
tmp = tmp->next;
}
List i;
for (i = left; i != right; i = i->next)
{
cout << i->data << " ";
}
cout << i->data;
}
