23. 연속 부분 증가수열

이 문제의 저작권은 인프런 강의 "it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비" 에 있습니다.

 

 

 

 

문제 23

 

N개의 숫자가 나열된 수열이 주어집니다. 이 수열 중 연속적으로 증가하는 부분 수열을 최대 길이를 구하여 출력하는 프로그램을 작성하세요. 만약 N=9이고 5 7 3 3 12 12 13 10 11 이면 “3 3 12 12 13” 부분이 최대 길이 증가수열이므로 그 길이인 5을 출력합니다. 값이 같을 때는 증가하는 걸로 생각합니다.

 

 

입력예제

 

9

5 7 3 3 12 12 13 10 11

 

출력예제

 

5

 

 

---

먼저 pre, now 변수를 활용해서 코드를 짜보자.

pre는 이전 값을, now는 현재 값을 의미한다고 정의한다.

5 7 3 3 12 12 13 10 11 에서 5는 pre를 7은 now로 정의해서 이 둘을 비교 후, now가 더 크니까 cnt의 값을 1 증가시켜준다. 그 다음 7을 pre로 정의하고 3은 now로 정의한 후, 비교했을 때 크지 않으므로 cnt의 값은 세어주지 않는다. (길이=1)

 

알고리즘을 정리해보면

1. pre = 5로 먼저 정의하고 now는 그 다음 값

2. pre와 now를 비교했을 때 now가 크면 cnt 1 증가

3. 크지 않으면 (else) cnt = 1 그대로

4. pre=now로 해서 now값을 이전 값으로 치환해주기

 

#include <stdio.h>
using namespace std;


int main(){
	freopen("input.txt", "rt", stdin);
	int n, i, pre, now, cnt, max;
	
	scanf("%d", &n);
    scanf("%d", &pre);
    
    cnt=1;
    max=1;
    
    for(i=2; i<=n; i++){
    	scanf("%d", &now);
        if(pre<=now) cnt++;
        else cnt=1;
        if(cnt>max) max=cnt;
        
        pre=now;
        }
        
    printf("%d", max);
	return 0;
	
}