[JAVA]백준 10819번: 차이를 최대로

www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

1. 문제 설명

 

N개의 정수가 주어질 때 |A [0] - A [1]| + |A [1] - A [2]| +... + |A [N-2] - A [N-1]|의 식이 최댓값을 구하는 문제이다.

 

N개의 정수로 순열을 만들고 식을 계산하여 최댓값을 구하면 된다.

 

순열 알고리즘의 경우 재귀함수 알고리즘을 사용했는데 좀 더 효율적인 순열 알고리즘으로 대체하면 좋을 듯하다.

 

2. 코드

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int[] array=new int[9];
    public static int[] list=new int[9];
    public static boolean[] flag=new boolean[9];
    public static int num;

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        num=scan.nextInt();

        for(int i=0;i<num;i++)
            array[i]=scan.nextInt();

        int sum=0;
        int max=0;

        for(int i=0;i<num;i++){
            list[0]=array[i];
            flag[i]=true;
            sum=make_list(1);
            flag[i]=false;

            if(sum>max)
                max=sum;
        }

        System.out.println(max);


        scan.close();
    }

    public static int make_list(int index){

        if(index==num){
            int sum=0;

            for(int i=0;i<num-1;i++)
                sum+=Math.abs(list[i]-list[i+1]);


            return sum;
        }

        int max=0;

        for(int i=0;i<num;i++){
            if(!flag[i]){
                list[index]=array[i];
                flag[i]=true;
                int temp=make_list(index+1);
                flag[i]=false;

                if(temp>max)
                    max=temp;
            }
        }

        return max;
    }




}