package Math;

import java.util.*;

//30min
public class beak_연속합 {
	
	//당연하게도 10만씩 for돌리면 100억이라서 에러나는 문제..
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int arr[] = new int[n];
        int dp[] = new int[n];
        
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        
        dp[0] = arr[0];
        
        for(int i=1;i<n;i++){//내 전과 더한게 크면 넣고 or 내가 더크면 나부터 다시 시작!
            dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
        }
        
        int max = dp[0]; // max값을 당연히 0으로 초기화하면 값이 틀릴 수 도 있다는 점!!!
        for(int i=1;i<n;i++)
            max = Math.max(max, dp[i]);
        
        
        System.out.println(max);
    }
}

package Greedy;

import java.util.*;

//30min
public class beak_로프 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[] = new int[n];
		
		for(int i=0;i<n;i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		int size = 1;
		int max = 0;
		
		//제일 작은 숫자 * size가 답이 아니고 중량으로 칠 수 있는거 * size가 제일 큰게 답이라는것!
		for(int i=arr.length-1; i>=0; i--) {
			max = Math.max(max, arr[i] * size);
			size++;
		}
		
		System.out.println(max);
	}
}

package Dynamic_programming;

import java.util.*;

//30min
public class beak_포도주시식 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[] = new int[n+1];
		int dp[] = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			arr[i] = sc.nextInt();
		}
				
		//1. dp1의 최대는 1잔 마셨을 경우
		dp[1] = arr[1];
		
		//2. dp2의 최대는 -> 1잔 + 2잔
		if(n>1) // n이 1일 수도 있기 때문에, n이 1일때는 arr[2] 없으므로 -> n>1라는 조건 걸어준다.
			dp[2] = arr[1] + arr[2];
		
		//3. dp3 부터는 계산 가능
		//연속으로 0잔 마실 경우 || 연속으로 1잔 || 연속으로 2잔   ->>마신 경우들의 max 값 넣기
		for(int i=3; i<=n; i++) { // i로 초기화했으면 i를 써야지 n을 쓰면 어떡하니!
			dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]));
		}
		
		System.out.println(dp[n]);
	}
}

// https://limkydev.tistory.com/112

package Dfs_Bfs;
import java.util.*;


//35min
public class beak_안전영역 {

	static int[][] color(int arr[][], int n) {
		
		for(int i=0;i<arr.length; i++) {
			for(int j=0;j<arr.length; j++) {
				if(arr[i][j] <=n)
					arr[i][j] = 0;
			}
		}
		
		return arr;
	}
	
	static void dfs(int arr[][], int x, int y) {
		arr[x][y] =0;
		
		int dx[] = {0,0,1,-1};
		int dy[] = {1,-1,0,0};
		
		for(int i=0; i<4;i ++) {
			int newx = x + dx[i];
			int newy = y + dy[i];
			
			if(newx>=0 && newx<arr.length && newy>=0 && newy<arr.length && arr[newx][newy]!=0)
				dfs(arr,newx,newy);
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[][] = new int[n][n];
		int height [] = new int[101];
		
		int answer = 1; // 전부 물에 잠기지 않을경우는 영역이 1개이기 떄문에 초기화를 0이아니고 1로 해주어야 한다 
		
		for(int i=0;i<n;i++) {
			for(int j=0; j<n;j++) {
				int a = sc.nextInt();
				arr[i][j] = a;
				height[a] = 1;
			}
		}
		
		for(int i=1;i<height.length;i++) {
			if(height[i] == 1) {
				
				int new_arr[][] = new int[n][n]; //arr 배열을 new_arr배열 만들어서 돌려보는 법!
				
				for(int k=0; k<n; k++) {
					for(int l=0; l<n; l++) {
						new_arr[k][l] = arr[k][l]; // new_arr에 arr 넣기 -> 이걸 반복해줘야 arr여러번 사용 가능
					}
				}
				
				new_arr = color(new_arr,i);
				
				int max = 0;
				for(int k=0; k<n; k++) {
					for(int l=0; l<n; l++) {
						if(new_arr[k][l] !=0) {
							dfs(new_arr,k,l);
							max++;
						}
					}
				}//middle for
				
				answer = Math.max(answer, max);
				
			}//if
		}//out for
		
		System.out.println(answer);
		
	}
}