[BOJ] 1744. 수 묶기

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	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 answer = plusSum(arr) + minusSum(arr);											
		System.out.println(answer);
	}
	
	public static int plusSum(int[] arr) {		
		int plus_index = findPlusIndex(arr);
		if(arr[arr.length - 1] <= 0) return 0;
		int temp = (arr.length - 1) % 2;
		int after_index_value = 0;
		int sum = 0;				
		for(int i = arr.length - 1; i > plus_index; i--) {
			if(i % 2 == temp) after_index_value = arr[i];
			else sum += Math.max(arr[i] * after_index_value, arr[i] + after_index_value); 
		}
		if((plus_index + 1) % 2 == temp) sum += arr[plus_index + 1];
		return sum;
	}
	
	public static int minusSum(int[] arr) {
		int minus_index = findMinusIndex(arr);
		if(arr[0] >= 0) return 0;
		int before_index_value = 0;
		int sum = 0;
		for(int i = 0; i < minus_index; i++) {
			if(i % 2 == 0) before_index_value = arr[i];
			else sum += before_index_value * arr[i];
		}
		if((minus_index - 1) % 2 == 0) {
			if(!isExistsZero(arr)) sum += arr[minus_index - 1];			
		}
		return sum;
	}
	
	public static int findMinusIndex(int[] arr) {
		int minus_index = arr.length;
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] >= 0) {
				minus_index = i;
				break;
			}
		}
		return minus_index;
	}
	
	public static int findPlusIndex(int[] arr) {
		int plus_index = -1;
		for(int i = arr.length - 1; i >= 0; i--) {
			if(arr[i] <= 0) {
				plus_index = i;
				break;
			}
		}
		return plus_index;
	}
	
	public static boolean isExistsZero(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] == 0) {
				return true;
			}
		}
		return false;
	}
}