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

문제에서 조심해야할 점은 바이토닉 부분 수열 이라는 점이다 바이토닉 수열이 아니라는것 

바이토닉 수열에서 바이토닉은 특정값을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순인 수열을 말한다

문제에서 말하는 수열은 바이토닉 부분 수열은 힌트에서도 볼 수 있다 싶이

{ 1 5 2 1 4 3 4 5 2 1 }

이렇다고 볼 수 있는데 즉 굵게 칠해진 부분이 바이토닉 부분 수열이고 그 중간에 끼는 5 1 4와 같이 흐름에 맞지않는 수는 빼고 개수를 세면 된다는 것이다.

 

이때 계산해야할점은 앞에서 올라가는 수와 뒤에서 올라오는 수를 더한값이 가장 큰것을 찾아야한다는점인데 

이말인 즉, 앞에서 올라가는 수열의 최대값 과 뒤에서 올라가는수열의 최대값을 더해야한다는 것이다.

 

표로보면 아래와같다

입력수열	바이토닉	값
1	1	1
5	1,5	2
2	1,(5),2	2
1	1,(5,2,1)	1
4	1,(5),2,(1),4	3
3	1,(5),2,(1,4),3	3
4	1,(5),2,(1,4),3,4	4
5	1,(5),2,(1,4),3,4,5	5
2	1,(5,2,1,4,3,4,5),2	2
1	1,(5,2,1,4,3,4,5,2,1)	1

즉

1	5	2	1	4	3	4	5	2	1
1	2	2	1	3	3	4	5	2	1

오름차순은 이 값과 같고

 

내림차순은

입력수열	바이토닉	값
1	1	1
2	1,2	2
5	1,2,5	3
4	1,2,(5),4	3
3	1,2,(5,4),3	3
4	1,2,(5,4),3,4	4
1	1,(2,5,4,3,4,1)	1
2	1,(2,5,4,3,4,1),2	2
5	1,2,(5,4),3,4,(1,2),5	5
1	1,(2,5,4,3,4,1,2,5,1)	1

이값과 같으며 즉 아래와같다

1	5	2	1	4	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

 

 

두배열을 나란히 보면

앞에서 올라가는 A

1	5	2	1	4	3	4	5	2	1
1	2	2	1	3	3	4	5	2	1

뒤에서 올라오는 B

1	5	2	1	4	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

각 값을 합쳤을때 가장 큰수는 파란색 글자인 5+3 인 8이다

즉 A는 1,2,3,4,5 가 되겠고 B는 1,2,5 가 되겠다 이때 바이토닉수열은 1,2,3,4,5,5,2,1 처럼 보이겠지만 5는 겹쳐져있는것이니 빼주면 결과값은 1,2,3,4,5,2,1 이 되겠고 출력은 7이 되어야겠다

 

이를 코드로 작성해보자

코드 작성

입력받는 수들을 쪼개어 배열에 담아준다

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

public class training {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int A = Integer.parseInt(br.readLine());
		String[] string = br.readLine().split(" ");
		int[] list = new int[A];
		for (int i = 0; i < A; i++) {
			list[i] = Integer.parseInt(string[i]);
		}

 

왼쪽에서 오른쪽으로 올라가는 수열 계산

int[] left = new int[A];
for (int i = 0; i < A; i++) {
    for (int j = i; j >= 0; j--) {
        if (list[i] > list[j]) {
            left[i] = Math.max(left[i], left[j] + 1);
        }
    }
}

오른쪽에서 왼쪽으로 올라가는 수열 계산

int[] right = new int[A];
for (int i = A - 1; i >= 0; i--) {
    for (int j = i; j < A; j++) {
        if (list[i] > list[j]) {
            right[i] = Math.max(right[i], right[j] + 1);
        }
    }
}

 

최대값 계산

int Max = 0;
for (int i = 0; i < A; i++) {
    Max = Math.max(left[i] + right[i], Max);
}
System.out.println(Max + 1);

 

결과