1. 最小战力

你在玩一款游戏，在游戏中你不断地打倒敌人，并强化自己的战斗力。
这个游戏中没有小怪，只有若干个 boss，你把所有 boss 全部打败即完成游戏。
打 boss 的顺序可以自选。为了让你们计算起来更加轻松，我大大简化了每个 boss 的属性，
每个 boss 只有两项属性：
击败它需要的战斗力数值（大于等于该数值即可击败）、击败它之后，
你可以永久获得的战斗力增加数值。在游戏的开始，你可以获得一定的战斗力，
且这个战斗力与你花的钱成正比。你当然想尽可能地省钱，
因此请你计算出能够通关的的前提下，一开始获得的最小战斗力。

输入描述

第一行整数 n，表示 boss 数量。1 <= n <= 100000
后面 n 行，每行两个空格隔开的整数 x, y，表示击败这个 boss 需要的战斗力数值，击败它之后，你可以永久获得的战斗力增加数值。0 <= x, y <= 1000000000。

输出描述

一个整数，表示能通关的情况下，一开始获得的最小战斗力数值。

100%。

public static void minInputVal() {
    Scanner scanner = new Scanner(System.in);
    int number = Integer.parseInt(scanner.nextLine().trim());
    List<int[]> vals = new ArrayList<>();
    for (int i = 0; i < number; i++) {
        String[] s = scanner.nextLine().trim().split(" ");
        vals.add(new int[]{Integer.parseInt(s[0]), Integer.parseInt(s[1])});
    }
    vals.sort(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if(o1[0] != o2[0]) return o1[0] - o2[0];
            return o2[1] - o1[1];
        }
    });

    int money = 0, initMoney = 0;
    for (int[] val : vals) {
        if(money < val[0]){
            initMoney += val[0] - money;
            money = val[0];
        }
        money += val[1];
    }
    System.out.println(initMoney);
}

2. 序列重排

给一个长度为n的序列A，你可以将序列中的元素按任意顺序重新排列，请你找到一种排列方式使得相邻两个数的差值之和最大，你只需要输出这个最大值即可。

输入描述

第一行整数 n，表示 boss 数量。1 <= n <= 100000
后面 n 行，每行两个空格隔开的整数 x, y，表示击败这个 boss 需要的战斗力数值，击败它之后，你可以永久获得的战斗力增加数值。0 <= x, y <= 1000000000。

输出描述

一个整数，表示能通关的情况下，一开始获得的最小战斗力数值。

采用最粗暴做法，通过27%，超时。还是记录下：

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = Integer.parseInt(scanner.nextLine().trim());
    String[] s = scanner.nextLine().trim().split(" ");
    List<Integer> vals = new ArrayList<>();
    HashMap<Integer, Integer> visited = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int key = Integer.parseInt(s[i]);
        vals.add(key);
        visited.put(key, visited.getOrDefault(key, 0) + 1);
    }
    vals.sort(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });

    List<List<Integer>> res = new ArrayList<>();
    dfs(vals, new ArrayList<Integer>(), res, visited);

    int maxVal = Integer.MIN_VALUE;
    for (List<Integer> re : res) {
        maxVal = Math.max(maxVal, calcSum(re));
    }
    System.out.println(maxVal);
}

private static int calcSum(List<Integer> temp) {
    int res = 0;
    for (int i = 1; i < temp.size(); i++) {
        res += Math.abs(temp.get(i - 1) - temp.get(i));
    }
    return res;
}

private static void dfs(List<Integer> vals, ArrayList<Integer> temp, List<List<Integer>> res,
                        HashMap<Integer, Integer> visited) {
    if(temp.size() == vals.size()){
        res.add(new ArrayList<>(temp));
        return;
    }

    for (int i = 0; i < vals.size(); i++) {
        int key = vals.get(i);
        if(i != 0 && vals.get(i - 1) == key) continue;
        if(visited.get(key) > 0){
            visited.put(key, visited.get(key) - 1);
            temp.add(key);
            dfs(vals, temp, res, visited);
            temp.remove(temp.size() - 1);
            visited.put(key, visited.get(key) + 1);
        }
    }
}

该怎么做？