DP #11054: 가장 긴 바이토닉 부분 수열 [JAVA]

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

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

 

 

---

 

내 힘으로 풀어서 기분이 조타♬

 

 

 

 

 

문제 접근

 

 

 

 

seq[i]를 기준으로 왼쪽에서 부분 증가 수열의 최대 길이를 찾고

오른쪽으로 부분 감소 수열의 최대 길이를 찾자.

 

그 후, 바이토닉 수열의 최대 길이를 찾자.

 

 

 

 

 

 

 

 

 

 

 

코드

 

 

 

 

 

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

public class Main {

	static Integer[] inc;
	static Integer[] dec;
	static int[] seq;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		seq = new int[N];
		inc = new Integer[N];
		dec = new Integer[N];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < N; i++) {
			increase(i);
			decrease(i);
		}

		int max = inc[0] + dec[0] - 1;

		for (int i = 0; i < N; i++) {
			if (inc[i] + dec[i] - 1 > max) {
				max = inc[i] + dec[i] - 1;
			}
		}

		System.out.println(max);

	}

	public static int increase(int n) {

		if (inc[n] == null) {

			inc[n] = 1;

			for (int i = n - 1; i >= 0; i--) {
				if (seq[i] < seq[n]) {
					inc[n] = Math.max(1 + increase(i), inc[n]);
				}
			}
		}

		return inc[n];
	}

	public static int decrease(int n) {

		if (dec[n] == null) {

			dec[n] = 1;

			for (int i = n + 1; i < seq.length; i++) {
				if (seq[i] < seq[n]) {
					dec[n] = Math.max(1 + decrease(i), dec[n]);
				}
			}
		}
		return dec[n];
	}

}