原题链接：后缀表达式

题目描述

给定 $N$ 个加号、$M$ 个减号以及 $N+M+1$ 个整数 $A_1,A_2,⋅⋅⋅,A_{N+M+1}，$小明想知道在所有由这 $N$ 个加号、$M$ 个减号以及 $N+M+1$ 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 $123+−$，则 $“23+1−”$ 这个后缀表达式结果是 $4$，是最大的。

输入格式

第一行包含两个整数 $N$ 和 $M。$

第二行包含 $N+M+1$ 个整数 $A_1,A_2,⋅⋅⋅,A_{N+M+1}。$

输出格式

输出一个整数，代表答案。

数据范围

$0≤N,M≤10^5,$
$−10^9≤A_i≤10^9$

输入样例1：

1 1
1 2 3

输出样例1：

4

思路

首先什么是后缀表达式？

后缀表达式也称为逆波兰式，就是一种计算机比较喜欢的存储方式，具体计算就是利用栈，如果遇到数字就压栈，遇到运算符就弹出两个数字，运算的结果再压栈。 逆波兰式也可以化为一颗二叉树，逆波兰式就是这颗二叉树的后序遍历

本道题要发现一个关键的点，那就是负号如果不为 $0$ 的 话，那么负号其实可以取 1 ~ m + n 个

• m == 0，那么结果就是所有的数相加
• m > 0
• 因为表达式调换运算的优先级，其实可以变为例如 $- (n - m)$，那么括号中的负号就会变为正号，负号就减少一个，一直可以减少到只有一个负号的情况 $-(a_1 - a_2 - a_3 -....- a_n)$ ，所以负号的取值个数左边界是 $1$ 个
• 而如果括号中是正号 $-(n + m)$，那么负号的个数就会多一个，因为正号是 $n$ 个，所以负号可以一直增加到 $n + m$，所以负号的取值个数右边界是 $n + m $ 个

总而言之，不管正号有多少个，只要负号大于 $0$ 个，那么运算过程中对数加还是减都可以随意，为了结果最大，遇到负数就减去，遇到正数就加上

因为如果 $m > 0$ ，则必须要有一个减去的数，就减去最小值，因为第一个数默认是加上的，所以也要加上一个数，加上最大值

时间复杂度

$O(nlogn)(排序)$ 或者 $O(n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long LL;

const int N = 100010 * 2;
int a[N];
int n, m;

int main()
{
    cin >> n >> m;
    int k = n + m + 1;
    for(int i = 0;i < k;i ++) scanf("%d",&a[i]);

    sort(a,a + k);  // 找最小值和最大值
    LL res = 0;
    if(!m) {
        for(int i = 0;i < k;i ++) res += a[i];
    }else {
        res = a[k - 1] - a[0];
        for(int i = 1;i < k - 1;i ++) res += abs(a[i]);
    }

    printf("%lld\n",res);
    return 0;
}