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

 

문제 링크 https://www.acmicpc.net/problem/11054

KEY

가장 긴 증가하는 부분 수열 문제와 풀이 과정이 거의 같다. 참고 --> https://everydayyy.tistory.com/136

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

위 글을 간단히 요약하자면, 가장 긴 증가하는 부분수열는 다음과 같이 구할 수 있다.

현재 자신과 이전에 나왔던 수들을 비교해가면서, 현재 자신 > 이전의 수를 만족할 경우에 길이+1을 해주고, 그 중 가장 긴 길이를 자신의 길이로 취한다.

 

이 문제와 같은 경우 가장 긴 감소하는 부분수열의 길이도 고려해야 하지만, 

수열을 뒤집어버린다면 결국 가장 긴 증가하는 부분수열의 길이를 2번 구함으로써 문제를 해결할 수 있다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX = 1001;
int n;
int arr[MAX];
int dp[MAX] = { 1, };
int rdp[MAX] = { 1, };
int answer;
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    //dp배열에는 증가하는 부분 수열의 길이 넣기 
    for (int i = 0; i < n; i++) {
        int value = 0;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                value = max(value, dp[j]);
            }
        }
        dp[i] = value + 1;
    }
    
    //rdp배열에는 수열을 거꾸로 한다음 증가하는 부분수열의 길이 넣기
    for (int i = n-1; i >= 0; i--) {
        int value = 0;
        for (int j = n-1; j >= i; j--) {
            if (arr[i] > arr[j]) {
                value = max(value, rdp[j]);
            }
        }
        rdp[i] = value + 1;
    }
 
    //정답은 dp+rdp중에 가장 큰 것
    for (int i = 0; i < n; i++) {
        answer = max(answer, dp[i] + rdp[i] - 1);
    }
    cout << answer;
 
}