카테고리 없음

[백준] 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();

    }

}