[백준 2491번] 수열 (C++)

문제링크 : https://www.acmicpc.net/problem/2491

 

#include <bits/stdc++.h> 
using namespace std;

int n, k, result = 0;
int arr[100001], dp[100001], dp2[100001];

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		dp[i] = dp2[i] = 1;
	}

	for (int i = 1; i < n; i++)
	{
		if (arr[i] >= arr[i-1])    //값이 연속해서 커지는 경우
		{
			dp[i] = max(dp[i], dp[i - 1] + 1);
		}
		if (arr[i] <= arr[i - 1])  //값이 연속해서 작아지는 경우
		{
			dp2[i] = max(dp2[i], dp2[i - 1] + 1);
		}
	}
	sort(dp, dp + 100001);
	sort(dp2, dp2 + 100001);
	cout << max(dp[100000], dp2[100000]);  //각 dp 배열에서 가장 큰 값을 출력
}

연속해서 커지는 경우, 연속해서 작아지는 경우 2가지를 각각 계산하여 이 중에서 큰 값을 출력한다.