[백준 Java] 11054 가장 긴 바이토닉 부분수열

[문제 링크] boj 11054 가장 긴 바이 토닉 부분 수열 자바 풀이 

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

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

 

[생각 흐름]

전에 풀었던 11053 https://www.acmicpc.net/problem/11053 (가장 긴 증가하는 부분 수열) 문제와 유사한 풀이 방법으로 해결했다.

앞에서부터 arr [i]를 포함한다는 전제로 arr [i]보다 작고 arr [j]까지의 최대 증가 부분 수열(sum [j])가  sum [i] 보다 크다면 

sum[i] = sum[j]+1 과 같은 방식으로 앞에서부터 뒤로 증가하는 부분 수열을 구했다.

뒤에서부터 증가하는 수열은 위 과정을 반대로 계산하면 된다.

 

그 후에 (0~i 까지의 증가하는 부분 수열의 최댓값) + (i~end까지의 감소하는 부분 수열의 최댓값) 의 합 중 가장 큰 값을 리턴하였다.

+ 초기값은 기본적으로 자기를 포함하는 부분 수열의 길이가 1 임으로 초기값은 1로 저장해 두고 마지막에는 i가 두 번 더해지므로 1을 빼도록 했다.

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;


        int numberCount = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int arr[] = new int[numberCount];
        int sum[] = new int[numberCount];
        int sum2[] = new int[numberCount];


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

//앞에서 부터 계산
        for(int i=0;i<numberCount;i++){
            sum[i]=1;
            for(int j=0;j<i;j++)
                if(arr[i]>arr[j] && sum[i]<=sum[j])sum[i] = sum[j]+1;
        }
//뒤에서 부터 계산
        for(int i=numberCount-1;0<=i;i--){
            sum2[i]=1;
            for(int j=numberCount-1;i<j;j--)
                if(arr[i]>arr[j] && sum2[i]<=sum2[j])sum2[i] = sum2[j]+1;
        }
//앞에서 부터 i위치 + i위치 부터 마지막까지의 최댓값을 저장 해서 출력한다.
        int max = 0;
        for(int i=0;i<numberCount;i++)
            max = Math.max(sum[i]+sum2[i]-1,max);

        System.out.println(max);

    }
}