算式最大值

给定:

1. $N$ 个正整数 $A_1,A_2, ... A_N$;
2. $P$ 个加号 + 和 $Q$ 个减号 -; ($P+Q=N-1$)
3. $K$ 对括号 ()

请你使用全部整数、加减号和括号，组成一个合法的算式 ($A_1~A_N$ 在算式中的顺序随意)，使得算式的结果最大

注意加减号只能作为二元运算符出现在算式中，不能作为正负号

括号可以出现在算式最左和最右，例如 (((1+2))) 是合法的

例如对于样例数据，(2-1)+3 或 3+(2-1) 等都是结果最大的算式

【输入】

第一行包含 4 个整数 $N,P,Q$ 和 $K$

第二行包含 $N$ 个正整数 $A_1$,A_2, ... A_N$

$2 ≤ N ≤ 100$
$P+Q+1=N$
$0 ≤ K ≤ 10$
$1 ≤ A_i ≤ 1000$

【输出】

最大算式结果

【样例输入】

3 1 1 1
1 2 3

【样例输出】

4

首先考虑没有括号的情况，如果没有括号，把 $N$ 个数降序排列，将 $p + 1$ 个最大的数加起来，减去剩下的 $Q$ 个数

如果有括号，总能通过括号将 $Q$ 个减号变为 $Q-1$ 个加号，例如输入

5 0 4 2
5 4 3 2 1

通过括号可使得整个表达式变为

5 - ((1 - 2 - 3 - 4))

一般地，对于任意带有括号的表达式，总能转化为 a - (b - c - d - ...) 的形式，此时只需要 b 最小，就能使整个表达式的值最大

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

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int p = cin.nextInt(); // +
        int q = cin.nextInt(); // -
        int k = cin.nextInt(); // ()
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) 
            arr[i] = cin.nextInt();
        
        Arrays.sort(arr, Collections.reverseOrder()); // Order by desc
        int ans = 0;
        if (k == 0) {
            for (int i = 0; i <= p; i++) 
                ans += arr[i];
            for (int i = p - 1; i < n; i++)
                ans -= arr[i];
        } else {
            for (int i = 0; i < n - 1; i++)
                ans += arr[i];
            ans -= arr[n - 1];
        }
        System.out.println(ans);
    }
}