<Algorithm> 16. 10819번 차이를 최대로

1. 10819번 차이를 최대로

• 순열을 활용하여 모든 경우의 수에 대한 차이값을 구하고 최댓값을 변화시켜준다.

• 주의할점은 입력의 순서대로가 아닌 임의로 들어올 경우 sort를 반드시 해주어야 한다.  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
 
    static int max=-1;
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        String[] in=br.readLine().split(" ");
        int[] input=new int[in.length];
        
        for(int i=0;i<in.length;i++) {
            input[i]=Integer.parseInt(in[i]);
        }
        Arrays.sort(input);
        
        div(input);
        permetation(input);
        
        System.out.println(max);
        
        
    }
    
    public static void permetation(int[] input) {
        int i=input.length-1;
        int j=input.length-1;
        
        while(i>0) {
            if(input[i-1]<input[i]) {
                break;
            }
            i--;
        }
        
        if(i==0) return;
        
        while(i<=j) {
            if(input[i-1]<input[j]) {
                int temp=input[i-1];
                input[i-1]=input[j];
                input[j]=temp;
                break;
            }
            j--;
        }
        
        j=input.length-1;
        
        while(i<j) {
        
            int temp=input[j];
            input[j]=input[i];
            input[i]=temp;
            i++;
            j--;
        }        
        
        div(input);
        permetation(input);
            
        
    }
    public static void div(int[] input) {
        int result=0;
        
        for(int i=0;i<input.length-1;i++) {
            result+=Math.abs(input[i]-input[i+1]);
        }
        if(max<result) {
            max=result;
        }
        
    }
    
}