백준 2491 수열 C++

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

2491번: 수열

---

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

---

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

---

해결방안 -> 

먼저 연속해서 커지는 것 중 길이가 최대인 것을 표현하는 DP배열(MAX) , 연속해서 작아지는 것 중 길이가 최대인 것을 표현하는 DP배열(MIN) 2개를 만들고
1로 채워준다.

for문을 MAX배열 , MIN배열 각각 한번씩 돌면서
N까지 돌면서 연속해서 커지거나 같으면 MAX배열 + 1,
N까지 돌면서 연속해서 작아지거나 같으면 MIN 배열 + 1,
최대 길이는 for문 2번 돌떄마다 각각 갱신해주면 MAX,MIN배열의 최대 길이가 갱신되서 나온다

---

#include <iostream>
using namespace std;
int arr[100010];
int Min[100010];
int Max[100010];
int main(void){
    int n;
    cin >> n;
    for(int i = 0;i<n;i++){
        Min[i] = 1;
        Max[i] = 1;
        cin >> arr[i];
    }

    int max_length = 1;

    for(int i = 1;i<n;i++){

        if(arr[i] >= arr[i-1]){
            Max[i] = Max[i-1] + 1;
        }
        if(Max[i] > max_length){
            max_length = Max[i];
        }


    }

    for(int i = 1;i<n;i++){

        if(arr[i] <= arr[i-1]){
            Min[i] = Min[i-1] + 1;
        }

        if(Min[i] > max_length){
            max_length = Min[i];
        }

    }
    cout << max_length;


}

#include <iostream>
using namespace std;
int arr[100010];
int Min[100010];
int Max[100010];
int main(void){
    int n;
    cin >> n;
    for(int i = 0;i<n;i++){
        Min[i] = 1;
        Max[i] = 1;
        cin >> arr[i];
    }
 
    int max_length = 1;
 
    for(int i = 1;i<n;i++){
 
        if(arr[i] >= arr[i-1]){
            Max[i] = Max[i-1] + 1;
        }
        if(Max[i] > max_length){
            max_length = Max[i];
        }
 
 
    }
 
    for(int i = 1;i<n;i++){
 
        if(arr[i] <= arr[i-1]){
            Min[i] = Min[i-1] + 1;
        }
 
        if(Min[i] > max_length){
            max_length = Min[i];
        }
 
    }
    cout << max_length;
 
 
}