最长连续递增子序列

叶茂林

发布于 2023-07-30 11:23:39

37400

代码可运行

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

运行总次数：0

代码可运行

题目描述

给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

输入

输入第1行给出正整数n（≤105）；第2行给出n个整数，其间以空格分隔。

输出

在一行中输出第一次出现的最长连续递增子序列，数字之间用空格分隔，序列结尾不能有多余空格。

输入样例1

15 1 9 2 5 7 3 4 6 8 0 11 15 17 17 10

输出样例1

3 4 6 8

思路分析

两层循环去找数组中每一个数后面有多少个连续递增的数，记录下来，一对一成一个新数组，然后遍历这个新数组找出最大的连续递增的所对应的数，然后从它开始循环输出，循环的次数就是连续递增的数目。

AC代码

#include <bits/stdc++.h>
using namespace std;
class Yezi{
	int*p=NULL,*increase=NULL,n;
	public:
		Yezi(){
			cin>>n;
			p=new int [n];
			increase=new int[n];
			for(int i=0;i<n;i++){
				cin>>p[i];
				increase[i]=1;
			}
		}
		void Answer(){
			for(int i=0;i<n-1;i++)
			for(int j=i;j<n-1;j++)
			if(p[j]<p[j+1])
			increase[i]++;
			else break;
			int maxbegin=0,index=0;
			for(int i=0;i<n;i++)
			if(increase[maxbegin]<increase[i])
			index=maxbegin=i;
			cout<<p[maxbegin++];
			while(--increase[index]){
				cout<<' '<<p[maxbegin++];
			}
		}
};
int main() {
	Yezi test;
	test.Answer();
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-09-20，如有侵权请联系 cloudcommunity@tencent.com 删除

int