카테고리 없음
[백준] 27210번 신을 모시는 사당 (gold 5
gomduri43
2023. 6. 21. 12:29
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
int a=Integer.parseInt(br.readLine());
StringTokenizer st=new StringTokenizer(br.readLine());
int[] num=new int[a];
for(int i=0; i<a; i++){
num[i]=Integer.parseInt(st.nextToken());
}
int[] dp=new int[a];
dp[0]= num[0]==1 ? 1 : -1;
int max=dp[0];
int min=dp[0];
for(int i=1; i<a; i++){
if(num[i]==1){
dp[i]=dp[i-1]+1;
}
else{
dp[i]=dp[i-1]-1;
}
max=max>dp[i] ? max: dp[i];
min=min<dp[i] ? min: dp[i];
}
int answer=0;
//왼쪽기준
int tempmin=0;
for(int i=0; i<a; i++){
if(dp[i]==max){
break;
}
tempmin= tempmin<dp[i] ? tempmin : dp[i];
}
answer=max-tempmin;
//오른쪽기준
int tempmax=0;
for(int i=0; i<a; i++){
if(dp[i]==min){
break;
}
tempmax= tempmax>dp[i] ? tempmax : dp[i];
}
answer= answer > (min-tempmax)*-1 ? answer : (min-tempmax)*-1;
bw.write(answer+"");
bw.flush();
}
}