[백준][dp] 11054 가장 긴 바이토닉 부분 수열 c++ 구현

목차

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

문제

 

 

참고

https://be-senior-developer.tistory.com/23

[백준][dp] 11053 가장 긴 증가하는 부분 수열 c++ 구현

위의 문제를 풀어보면 쉽게 접근할 수 있다.

 

 

문제 구현 방향

시작점에서 증가하는 가장 긴 수열과 끝점에서 증가하는 가장 긴 수열을 구해놓고 접근했다.(전 처리)

그 이후 이중 for문으로 둘을 합쳐 가장 큰 값을 구했다. (1000*1000이라 시간초과는 나지 않는다.)

합칠때 둘의 값 크기를 비교하는 것만 주의해주면 된다.

 

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;

int N;
int arr[10001] = { 0 };
//시작점 dp
int upDp[10001];

//끝점 dp
int upDpE[10001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        upDp[i] = 1;
        upDpE[i] = 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                upDp[i] = max(upDp[i], upDp[j] + 1);
            }
        }
    }
    for (int i = N-1; i >=0; i--) {
        for (int j = N-1; j > i; j--) {
            if (arr[i] > arr[j]) {
                upDpE[i] = max(upDpE[i], upDpE[j] + 1);
            }
        }
    }
    int m = 1;
    //합쳐서 가장 큰 것을 구해준다. 
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
        	//주의해야 할 부분 
            if(arr[i] > arr[j])
                 m = max(m, upDp[i] + upDpE[j]);
        }
    }
    cout << m;
    return 0;
   

}