23. 연속 부분 증가수열 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include<stdio.h>
#include<vector>

using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	
	vector<int> num(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &num[i]);
		
		
	vector<int> answer;
	int start = 0;
	int end = 1;
	int maxCount = 0;
	int count = 0;
	while(end < n)
	{
		if(num[start] <= num[end])
		{
			answer.push_back(num[start]);
			
			if(end == n-1)
			{
				answer.push_back(num[end]);
				count = answer.size();
			}
		}
		else
			{
				answer.push_back(num[start]);
				count = answer.size();
				answer.clear();
			}
			
		
		if(maxCount < count)
			maxCount = count;
		
		start++;
		end++;
	}
	
	printf("%d", maxCount);
	return 0;
}

1. 두 값을 비교해서 다음 값이 더 크다면 vector<int> answer 에 push_back 한다.

2. 다음 값이 더 작은 값이 나온다면 큰 값을 먼저 answer에 push_back 한 다음 size를 count에 할당하고 clear한다.

3. 반복하여 maxCount를 return한다.

 

!! 반례 !!

- 값이 계속해서 커지는 경우 맨 마지막 값은 answer에 포함되지 못한다.

ex) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10의 경우 9까지는 들어가지만 10은 들어가지 못한다.

따라서 end가 마지막인 n-1이 됐을 때, 이전 값보다 크다면 2번 작업을 반복한다.

 

첫 점수 : 80점(반례 못 찾음)