kingsubin

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int[] d;
    static int[] dl;
    static int[] dr;
    static int[] val;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        d = new int[n+1]; dl = new int[n+1]; dr = new int[n+1];
        val = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            val[i] = Integer.parseInt(st.nextToken());
        }

        // dl : i를 마지막으로하는 증가하는 부분 수열의 길이
        for (int i = 1; i <= n; i++) {
            dl[i] = 1;
            for (int j = 1; j <= i; j++) {
                if (val[j] < val[i] && dl[i] < dl[j] + 1) {
                    dl[i] = dl[j] + 1;
                }
            }
        }

        // dr : i를 시작으로하는 감소하는 부분 수열의 길이
        for (int i = n; i >= 1; i--) {
            dr[i] = 1;
            for (int j = i+1; j <= n; j++) {
                if (val[j] < val[i] && dr[i] < dr[j] + 1) {
                    dr[i] = dr[j] + 1;
                }
            }
        }

        // d = dl + dr - 1;
        for (int i = 1; i <= n; i++) {
            d[i] = dl[i] + dr[i] - 1;
        }

        int ans = 0; // 최댓값
        for (int i = 1; i <= n; i++) {
            if (ans < d[i]) ans = d[i];
        }

        System.out.println(ans);
    }
}

 

- 풀이법도 생각하고 거의 정답에 근접했는데 못 풀었다.

- i가 시작인 감소하는 부분수열에서 막혔다.

- 분명히 풀었던 문제인데 안되니까 답답하다,, 

- 주말엔 풀었던 문제를 다시 보자.

 

 

- d[i] = i가 Sk 일때의 바이토닉 수열의 길이라고 점화식 세움

- i가 Sk일경우 i가 마지막인 증가하는 부분 수열의 길이 , i가 시작인 감소하는 부분 수열의 길이와 같다.

- d[i] = dl[i] + dr[i] -1 ; i가 두 번 중복되니 마지막에 -1

- ans는 d[] 에서 최댓값