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

문제링크 : www.acmicpc.net/problem/11054

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

---

---

<알고리즘>

 이 문제에서는

   1) 왼쪽(index = 0)에서부터 자신보다 작은 수가 몇개인지 세는 수열 dq1

   2) 오른쪽(index= N-1)에서부터 자신보다 작은 수가 몇개인지 세는 수열 dq2

   3) 자신보다 양쪽(dq1+dq2)에 작은 수가 몇개인지 세는 수열 dq3

 이렇게 세개의 수열이 필요하다.  자신보다 작은 수가 몇개인지 세는 방법은 앞서한 11053번 문제를 참고해야한다.

 

  dq3를 통해 우리는 각 칸의 값이 양쪽으로 자신보다 작은 숫자의 개수가 몇개인지 확인할 수 있는데, 이때 dq1를 통해, dq2를 통해 자기자신값이 두번 더해지는 것을 기억하고 답을 출력할땐 -1을 해주어야한다.

 

  +) 2021.03.15 - [Baekjoon Online Judge] - 11053번 가장 긴 부분수열

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s="";
		try {s=bf.readLine();}catch(IOException e) {}
		int N = Integer.parseInt(s);
		try {s=bf.readLine();} catch(IOException e) {}
		StringTokenizer st = new StringTokenizer(s);
		ArrayList<Integer> number = new ArrayList<Integer>();
		for(int i =0;i<N;i++) {
			number.add(Integer.parseInt(st.nextToken()));
		}
		
		//0~N-1순으로 dq
		ArrayList<Integer> dq = new ArrayList<Integer>();
		for(int i =0;i<N;i++) {
			dq.add(1);
		} 
		for(int i =0;i<N;i++) {
			for(int j = 0;j<i;j++) {
				if(number.get(i)>number.get(j)) {
					dq.set(i, Math.max(dq.get(i),dq.get(j)+1));
				}
			}
		}
		
		//N-1~0순으로 dq
		ArrayList<Integer> dq2 = new ArrayList<Integer>();
		for(int i =0;i<N;i++) {
			dq2.add(1);
		} 
		for(int i =N-1;i>=0;i--) {
			for(int j = N-1;j>i;j--) {
				if(number.get(i)>number.get(j)) {
					dq2.set(i, Math.max(dq2.get(i),dq2.get(j)+1));
				}
			}
		}
		
		//양방향을 모두 고려한 결과
		ArrayList<Integer> dq3 = new ArrayList<Integer>();
		for(int i =0;i<N;i++) {
			dq3.add(1);
		}
		int max = 0;
		int maxInd = 0;
		for(int i =0;i<N;i++) {
			dq3.set(i, dq.get(i)+dq2.get(i));
			if(dq3.get(i)>max) {
				max = dq3.get(i);
				maxInd = i;
			}
		}
		System.out.println(max-1);
	}
}