作者:海纳百川2602902033 | 来源:互联网 | 2023-09-15 19:46
给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
输入格式:
输入第1行给出正整数n(\le 10^5≤105);;第2行给出n个整数,其间以空格分隔。
输入样例:
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10
输出样例:
3 4 6 8
思路:首先寻找存在最长子序列的序列长度和终止下标,接下来按要求输出。
如果序列长度为0,则最长递增子序列为第一个元素。
链表法和动态规划法未完待续。
代码如下:
include
using namespace std;
#define maxn 100005
int main()
{int n,count &#61; 0;int a[maxn];scanf("%d",&n);for(int i &#61; 0; i a[i-1]){count&#43;&#43;;if(count>j){j &#61; count;k &#61; i;}}elsecount &#61; 0;}int start &#61; k - j;int end &#61; k;if(j>0){int flag &#61; 0;for(int t &#61; start; t <&#61; end; t &#43;&#43;){if(!flag){printf("%d",a[t]);flag &#61; 1;}elseprintf(" %d",a[t]);}}elseprintf("%d",a[0]);}