문제 풀이

최장증가수열, 최장감소수열을 구하면된다.

연속한 수열에 대해 길이를 구해야 하므로 바로 전 원소만 체크해주면된다.

문제 링크

boj/2491

소스코드

PS/2491.cpp

#include<iostream>
#include<algorithm>
using namespace std;


int arr[100001];
int d[100001];
int d2[100001];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	for (int i = 0; i < n; i++)
	{
		d[i] = 1;
		d2[i] = 1;
	}
	int ans = 1;
	for (int i = 1; i < n; i++)
	{
		if (arr[i] >= arr[i - 1])
		{
			d[i] = d[i - 1] + 1;
			ans = max(ans, d[i]);
		}
	}
	for (int i = 1; i < n; i++)
	{
		if (arr[i] <= arr[i - 1])
		{
			
			d2[i] = d2[i - 1] + 1;
			ans = max(ans, d2[i]);
		}
	}

	cout << ans;
}