pta 문제 집 5 - 5 최 장 연속 증가 서브 시퀀스 (dp)

1608 단어 동적 계획동적 계획 - 선형 동규pat
순서 로 저 장 된 선형 표를 지정 합 니 다. 이 선형 표 에서 가장 긴 연속 증가 서브 시퀀스 를 찾 는 알고리즘 을 설계 하 십시오.예 를 들 어 (1, 9, 2, 5, 7, 3, 4, 6, 8, 0) 에서 가장 긴 증가 서브 서열 은 (3, 4, 6, 8) 이다.
입력 형식:
첫 번 째 줄 을 입력 하여 정수 nn (≤ 105 ≤ 10 5) 을 드 립 니 다.두 번 째 줄 은 N 개의 정 수 를 주 고 그 사이 에 빈 칸 으로 구분 합 니 다. 
출력 형식:
한 줄 에서 처음으로 나타 난 최 장 연속 증가 서브 시퀀스 를 출력 하고 숫자 간 에 빈 칸 으로 구분 하 며 시퀀스 의 끝 에 빈 칸 이 있어 서 는 안 됩 니 다.
입력 예시:
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10

출력 예시:
3 4 6 8
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int maxn=1e5;
int n;
int a[maxn+5];
int dp[maxn+5];
int search(int num,int l,int r)
{
	int mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(num>dp[mid])
			l=mid+1;
		else
			r=mid-1;
	}
	return l;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	memset(dp,0,sizeof(dp));
	dp[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(a[i]>a[i-1])
			dp[i]=dp[i-1]+1;
		else
			dp[i]=1;
	}
	int max=0;
	int pos=0;
	for(int i=n;i>=1;i--)
	{
		if(max<=dp[i])
		{
			max=dp[i];
			pos=i;
		}
	}
	for(int i=pos-dp[pos]+1;i<=pos;i++)
	{
		if(i!=pos)
		printf("%d ",a[i]);
		else
			printf("%d
",a[i]);
	}
	return 0;


}
백단 이 새로운 것 을 받아들이다.
javascript 원시 자료형 vs 참조 자료형 연습

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage