2846)오르막길

https://www.acmicpc.net/problem/2846

자질구레한 설명을 빼면 문제를 조금 더 쉽게 이해할 수 있다.

주어진 수열에서 증가하는 부분 수열을 찾고 부분 수열의 크기 중 최대인 것을 찾아야 한다.

부분 수열의 크기는 가장 마지막 항과 첫 째 항의 차로 얻은 값이다.

문제를 풀고 다른 사람의 풀이와 비교를 하니 뻘짓을 많이 했다.

부분 수열이 증가하는 지 알려면 이전 항의 크기와 현재 항의 크기를 비교해봐야 한다.

curHeight - preHeight > 0 이면 연속하는 두 개 항이 증가한다고 할 수 있다.

이 경우 이전 항의 값 preHeight와 현재 항의 값 curHeight를 배열 ascend에 넣는다.

위 그림처럼 부분 수열이 증가하는 경우 연속하는 항들을 ascend 배열에 넣고 있다.

그리고 오르막길이 아닐 경우 ascend의 첫째 항과 마지막 항(t번째 항)의 차이를 구하고 최대 값이라면 저장한다.

이처럼 분기하면 오르막길이 마지막으로 끝날 때 마지막 오르막길에서 최대값을 구할 수 없다.

그래서 반복문을 빠져 나온후 ascend의 마지막 항과 첫째 항을 빼는 작업을 해줘야 한다.

#include<stdio.h>
 
int main() {
    int N;
    int preHeight;
    int curHeight;
    int t = 0;
    int *ascent;
    int tempScale;
    int maxScale = 0;
 
    scanf("%d",&N);
    ascent = (int *)calloc(N,sizeof(int));
 
    scanf("%d", &preHeight);
    for (int i = 1; i < N;i++) {
        scanf("%d", &curHeight);
        if (curHeight - preHeight > 0) {
            ascent[t++] = preHeight;
            ascent[t] = curHeight;
        }
        else {
            tempScale = ascent[t] - ascent[0];
            if (tempScale > maxScale) {
                maxScale = tempScale;
            }
            t = 0;
        }
        preHeight = curHeight;
    }
    tempScale = ascent[t] - ascent[0];
    if (tempScale > maxScale) {
        maxScale = tempScale;
    }
    
    printf("%d\n",maxScale);
    
    return 0;
}