题目描述

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

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

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

输入格式

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

第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。

输出格式

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

数据范围

0≤N,M≤105,
−109≤Ai≤109

输入样例：

1 1
1 2 3

输出样例：

4

主要考点

逆波兰表达式
后序遍历二叉树
贪心

主要思想

根据负号个数分为两类：

1. 负号个数为0
   对策： 直接将各数相加即可

2. 负号个数大于0 (负号个数的范围为 1 ~ n + m + 1)
   对策：转化为一个负号的情况, 对各个数的绝对值求和.

易错点： 负号的个数不一定为 m

时间复杂度 ---- $O(n^2)$

C++代码

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;

const int N = 2e5 + 10;

int n, m;
int a[N];

int main(){
    cin >> n >> m;
    int k = n + m + 1;
    for(int i = 0; i < k; i ++) cin >> a[i];

    LL res = 0;
    if(!m){  //0个负号, 即均为正数, 将所有数直接相加即可
        for(int i = 0; i < k; i ++){
            res += a[i];
        }
    }
    else{  //存在负号, 负号个数为 1 ~ n + m + 1, 转化为1个负号的情况, 求得最大值
        sort(a, a + k);
        res = a[k - 1] - a[0];
        for(int i = 1; i < k - 1; i ++){
            res += abs(a[i]);
        }
    }

    cout << res << endl;

    return 0;
}