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

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

---

---

접근

• dp1[i]는 i번째일 때 증가 수열의 길이이다. (i는 0부터 n까지 증가)
• dp2[i]는 i번째일 때 증가 수열의 길이이다. (i는 n부터 0까지 감소)
• ans = dp1[i] + dp2[i] 이라고 한다면, ans는 (i번 째 수를 바이토닉 수열 중 가장 큰 수로 했을 때의 수열의 길이)+1 이 저장된다. 
• '+1'인 이유는 대칭성 때문. 
• 따라서, 정답은 ans-1이다. 

• dp1에 대한 for문을 살펴보자. 
• list[i] > list[j] : 이전 값 보다 큰 값이어야, 증가 수열이 되므로.
• tmp < dp1[j] : tmp에는 dp[1]부터 dp[j-1]까지 값 중 최댓값이 들어있다. 따라서, 이를 만족하면, 새로운 최댓값이 등장하였다는 뜻이므로, tmp값을 갱신해준다. 

 

 

---

코드

import java.util.*;
import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        int[] list = new int[n + 1];
        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];
        int tmp = 0;
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++)
            list[i] = Integer.parseInt(st.nextToken());
 
        dp1[0] = dp1[1] = dp2[n] = 1;
 
        for (int i = 1; i <= n; i++) {
            tmp = 0;
            for (int j = 1; j < i; j++) {
                if (list[i] > list[j] && tmp < dp1[j]) {
                    tmp = dp1[j];
                }
            }
            dp1[i] = tmp + 1;
        }
 
        for (int i = n; i >= 1; i--) {
            tmp = 0;
            for (int j = n; j > i; j--) {
                if (list[j] < list[i] && tmp < dp2[j]) {
                    tmp = dp2[j];
                }
            }
            dp2[i] = tmp + 1;
        }
 
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (ans < dp1[i] + dp2[i]) {
                ans = dp1[i] + dp2[i];
            }
        }
 
        bw.write((ans - 1) + "\n");
 
        bw.flush();
        br.close();
    }
}