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

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		int[] numReverse = new int[N];
		int[] numDpIncrease = new int[N];
		int[] numDpDecrease = new int[N];
		int[] result = new int[N];

		String[] tmp = br.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(tmp[i]);
			numReverse[N - i - 1] = num[i];
			numDpIncrease[i] = 1;
			numDpDecrease[i] = 1;
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				if (num[i] > num[j]) {
					numDpIncrease[i] = Math.max(numDpIncrease[i], numDpIncrease[j] + 1);
				}
				if (numReverse[i] > numReverse[j]) {
					numDpDecrease[i] = Math.max(numDpDecrease[i], numDpDecrease[j] + 1);
				}
			}
		}

		for (int i = 0; i < N; i++) {
			result[i] = numDpIncrease[i] + numDpDecrease[N-i-1] - 1;
		}
		
		Arrays.sort(result);
		
		System.out.println(result[result.length-1]);
	}
}

문제요약

가장 긴 바이토닉 부분 수열은?

S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열

설명

문제에 힌트가 있다.

S1 < S2 < ... Sk-1 < Sk 이 부분과

Sk > Sk+1 > ... SN-1 > SN 이 부분을 따로 생각해보자.

 

S1 < S2 < ... Sk-1 < Sk 이 부분은 0번째 인덱스 부터 증가하는 수열, 

Sk > Sk+1 > ... SN-1 > SN 아 부분은 N번째 인덱스 부터 증가하는 수열. 

 

따라서 

다음과 같이 입력값 | 입력값을 뒤집은 값을 나눈다.

 

수열을 진행하면서 해당 인덱스에서 가장 큰 길이를 가질 수 있는 것을 각각 정의해준다.

 

nomal에 해당 인덱스를 뒤집었기 때문에.

nomal[index] + reverse[N - index -1] 를 해준다면 1번과 2번을 합친 것이된다.

단, index 부분은 두 번 중복으로 수열을 처리했기 때문에 마지막에 -1을 해줘야 한다.

 

		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		int[] numReverse = new int[N];
		int[] numDpIncrease = new int[N];
		int[] numDpDecrease = new int[N];
		int[] result = new int[N];

		String[] tmp = br.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(tmp[i]);
			numReverse[N - i - 1] = num[i];
			numDpIncrease[i] = 1;
			numDpDecrease[i] = 1;
		}

초기설정이다.

한번에 반복문으로 모두 처리 가능하다.

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				if (num[i] > num[j]) {
					numDpIncrease[i] = Math.max(numDpIncrease[i], numDpIncrease[j] + 1);
				}
				if (numReverse[i] > numReverse[j]) {
					numDpDecrease[i] = Math.max(numDpDecrease[i], numDpDecrease[j] + 1);
				}
			}
		}

 

원래 배열, 뒤집은 배열에 해당 인덱스에 각각 가장 긴 수열을 계산해 주었다.

		for (int i = 0; i < N; i++) {
			result[i] = numDpIncrease[i] + numDpDecrease[N-i-1] - 1;
		}

원래 값과 뒤집은 값을 더해 result를 에 저장해준다. 단, 계산과정 중 중복으로 처리한 부분이 있어 -1을 해준다.