[알고리즘] 백준 - 차이를 최대로

백준 - 차이를 최대로

내 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class baekjoon_10819 {

    static boolean[] check;
    static int[] arr;
    static int ans = Integer.MIN_VALUE;
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        check = new boolean[N];

        String[] strInputs = br.readLine().split(" ");
        for (int i = 0; i < strInputs.length; i++) {
            arr[i] = Integer.parseInt(strInputs[i]);
        }
        solve(0, 0, Integer.MIN_VALUE);
        System.out.println(ans);
    }

    private static void solve(int count, int curSum, int prevValue) {
        if(count == N) {
            ans = Math.max(ans, curSum);
            return;
        }

        for (int i = 0; i < N; i++) {
            if(!check[i]) {
                check[i] = true;
                if (prevValue == Integer.MIN_VALUE) {
                    solve(count+1, curSum, arr[i]);
                } else {
                    solve(count+1, curSum + Math.abs(prevValue - arr[i]), arr[i]);
                }
                check[i] = false;
            }
        }
    }
}

처음에는 정렬을해서 풀어야하나 생각했다. 하지만 양수와 음수가 섞여있어 그렇게 풀면 쉽지않다. 또 N의 범위가 8까지로 매우 작은 것을 보고 힌트를 얻어 브루트포스로 풀었다.