[C++] 연속 부분 증가수열

📄문제

N개의 숫자가 나열된 수열이 주어집니다. 이 수열 중 연속적으로 증가하는 부분 수열을 최대길이를 구하여 출력하는 프로그램을 작성하세요.

만약 N=9이고 5 7 3 3 12 12 13 10 11 이면 “3 3 12 12 13”부분이 최대 길이 증가수열이므로 그 길이인 5을 출력합니다. 

값이 같을 때는 증가하는 걸로 생각합니다.

 

⬇️ 입력

첫 줄에 자연수의 개수 N(5<=N<=100,000)이 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 100,000이하의 자연수입니다.

9 5 7 3 3 12 12 13 10 11

 

⬆️ 출력

최대 부분 증가수열의 길이를 출력하세요.

5

 

📝 풀이

#include <iostream>

int main()
{
	int N;
	scanf_s("%d", &N);

	int curIncrementCnt = 1;
	int maxIncrementCnt = INT_MIN;

	int prevInput, curInput;

	scanf_s("%d", &prevInput);
	for (int i = 1; i < N; ++i)
	{
		scanf_s("%d", &curInput);

		if (curInput >= prevInput)
			++curIncrementCnt;
		else
			curIncrementCnt = 1;

		if (curIncrementCnt > maxIncrementCnt)
			maxIncrementCnt = curIncrementCnt;

		prevInput = curInput;
	}

	printf("%d", maxIncrementCnt);
}

• 이전 값을 임시로 저장하고, 현재 입력한 값과 비교하여 이전 값보다 크거나 같다면 증가하는 수열로 생각하여 계산합니다.