[백준] 11054번 : 가장 긴 바이토닉 부분 수열 with python3, cpp

25 Aug 2018

Reading time ~1 minute

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

n = int(input())
d = list(map(int, input().split()))
d.insert(0,0)

up_sequence = [0]+[1]*(n)
sequence = [0]+[1]*(n)
# i를 포함한 가장 긴 바이토닉 부분수열의 길이
ans = [0]*(n+1)
for i in range(1,n+1):
    for j in range(i):
        if d[j] < d[i] and up_sequence[i] < up_sequence[j] + 1:
            up_sequence[i] = up_sequence[j] + 1

for i in range(n-1, 0, -1):
    for j in range(i,n+1):
        if d[i] > d[j] and sequence[i] < sequence[j] + 1:
            sequence[i] = sequence[j] + 1
for i in range(1,n+1):
    ans[i] = up_sequence[i]+sequence[i] -1
print(max(ans))

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    vector<int> d(n);
    vector<int> d2(n);
    for (int i=0; i<n; i++) {
        d[i] = 1;
        for (int j=0; j<i; j++) {
            if (a[j] < a[i] && d[j]+1 > d[i]) {
                d[i] = d[j]+1;
            }
        }
    }
    for (int i=n-1; i>=0; i--) {
        d2[i] = 1;
        for (int j=i+1; j<n; j++) {
            if (a[i] > a[j] && d2[j]+1 > d2[i]) {
                d2[i] = d2[j]+1;
            }
        }
    }
    vector<int> ans(n);
    for (int i=0; i<n; i++) {
        ans[i] = d[i]+d2[i]-1;
    }

    cout << *max_element(ans.begin(), ans.end()) << '\n';
    return 0;
}

algorithm 백준