백준 11054 - 가장 긴 바이토닉 부분 수열

문제

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

11054번: 가장 긴 바이토닉 부분 수열

 

 

풀이

d[k] = A[k]을 포함하는 가장 긴 바이토닉 부분수열 이라고 하면

i = 1 부터 i = k 까지 가장 긴 증가하는 부분 수열과

i = N 부터 i = k 까지 가장 긴 증가하는 부분 수열을 구해서 더하면 된다.

이때 k번째는 겹치게 되므로 -1을 해준다.

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

11053번: 가장 긴 증가하는 부분 수열

 

 

코드

#include <iostream>
 
using namespace std;
 
int N, result;
int A[1001];
int dp[1001];
int dp2[1001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    
    for (int i = 1; i <= N; i++)
    {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (A[j] < A[i] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
        }
    }
 
    for (int i = N; i >= 1; i--)
    {
        dp2[i] = 1;
        for (int j = N; j > i; j--)
        {
            if (A[j] < A[i] && dp2[i] < dp2[j] + 1) dp2[i] = dp2[j] + 1;
        }
    }
    
    for (int i = 1; i <= N; i++)
    {
        if (result < dp[i] + dp2[i] - 1) result = dp[i] + dp2[i] - 1;
    }
    
    cout << result;
 
    return 0;
}