算式最大值

给定:

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);
    }
}