(11054) 가장 긴 바이토닉 부분 수열

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

단계별로 풀어보기

21단계(동적 계획법 1) 13번째

 

 

 

처음 풀 땐 굉장히 어렵게 생각했지만 사실 매우 간단하다. LIS를 정방향과 역방향으로 구한 뒤 어떤 인덱스 k에서 정방향 LIS의 최대값과 역방향 LIS의 최대값을 더한 뒤 (k번째 원소는 두 번 계산되므로) 1을 빼면 k번째 원소에서 꺾이는 바이토닉 부분 수열의 최대 길이다. k에 1부터 n까지 대입한 뒤 최대값을 찾으면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1), dp(n+1, 1), dp2(n+1, 1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  for(int i=2;i<=n;i++){
    for(int j=1;j<i;j++){
      if(v[j]<v[i])  dp[i]= max(dp[i], dp[j]+1);
    }
  }
  
  for(int i=n-1;i>=1;i--){
    for(int j=n;j>i;j--){
      if(v[j]<v[i])  dp2[i]= max(dp2[i], dp2[j]+1);
    }
  }
  
  int ans= 0;
  
  for(int i=1;i<=n;i++)  ans= max(ans, dp[i]+dp2[i]-1);
  
  cout << ans;
  
  return 0;
}