#백준_11054 가장 긴 바이토닉 부분 수열

백준

#백준_11054 가장 긴 바이토닉 부분 수열 - Java

ukyonge 2020. 1. 25. 16:22

# 유형 : 다이나믹 프로그래밍

# https://www.acmicpc.net/problem/11055, https://www.acmicpc.net/problem/11053, https://www.acmicpc.net/problem/11722 를 풀어봤다면 문제 접근은 어렵지 않다. 특정 인덱스 까지의 앞에서부터의 증가하는 부분수열 + 뒤에서부터의 증가하는 부분수열을 생각한다면 바로 풀 수 있다.

11722번: 가장 긴 감소하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

www.acmicpc.net

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

www.acmicpc.net


package bj;

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

public class p11054 {
	static int N;
	static int arr[];
	static int dp[];
	static int m_dp[];
	static int max=0;
	public static void main(String[] args) throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 N = Integer.parseInt(br.readLine());
		 arr = new int[N];
		 dp = new int[N];
		 m_dp = new int[N];
		 StringTokenizer st = new StringTokenizer(br.readLine());
		 for(int i=0; i<N; i++) {
			 arr[i] = Integer.parseInt(st.nextToken());
		 }
		 for(int i=0; i<N; i++) {
			 dp[i] = 1;
			 for(int j=0; j<i; j++) {
				 if(arr[i] > arr[j]) {
					 if(dp[i] < dp[j]+1)
						 dp[i] = dp[j]+1;
				 }
			 }
		 }
		 
		 for(int i=N-1; i>=0; i--) {
			 m_dp[i]=1;
			 for(int j=N-1; j>i; j--) {
				 if(arr[i] > arr[j]) {
					 if(m_dp[i] < m_dp[j]+1)
						 m_dp[i] = m_dp[j]+1;
				 }
			 }
		 }
		 for(int i=0; i<N; i++) {
			 max = Math.max(max, dp[i]+m_dp[i]-1);
		 }
		 System.out.println(max);
		 
	}
}