题目

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

请你输出这个最大的结果。
例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。

输入
第一行包含两个整数 N 和 M。
第二行包含 N + M + 1 个整数 A₁, A₂, · · · , A_N+M+1。
(对于所有评测用例，0≤ N,M ≤100000，−10⁹ ≤ Ai ≤10⁹。)

输出
输出一个数，表示答案

样例输入

1 1
1 2 3

样例输出

4

解题思路

首先是对后缀表达式运算过程的解读，样例给的“2 3 + 1 -”代表的是“2+3=5, 5-1=4”，因此，输出的就是4。

另外，一定要注意，题目样例没有反映出来的是，可以任意加上括号！！！ 有括号的前提下，减号将成为决定负数是否能够反转变为正数的关键，因此，根据减号有无考虑分类，如下：

1. 无减号时：所有数相加的和即为最大结果；

2. 有减号时：
   (1) 全是负数时，最大值 = 最大的负数+其余所有负数的绝对值，如：

   输入：
   1 1
   -1 -2 -3最大值：
   -1-((-2)+(-3))
   --------------------------------------------------------------------
   输入：
   1 2
   -1 -2 -3 -4最大值：
   -1-((-2)+(-3))-(-4)
   --------------------------------------------------------------------
   输入：
   2 3
   -1 -2 -3 -4 -5 -6最大值：
   -1-((-2)+(-3))-((-4)+(-5))-(-6)
   

   (2) 全是正数时，最大值 = 其余所有数的和-最小的正数，如：

   输入：
   1 1
   2 3 4最大值：
   3+4-2
   --------------------------------------------------------------------
   输入：
   1 2
   2 3 4 5最大值：
   3+4-(2-5) = 10 = 3+4+5-2
   

   (3) 既有正数，也有负数时，最大值 = 所有数的绝对值之和，如：

   输入：
   1 1
   2 -3 4最大值
   2+4-(-3)
   --------------------------------------------------------------------
   输入：
   2 1
   2 -3 4 -6最大值
   2+4-((-3)+(-6))
   

找到规律，此题便迎刃而解了。

（参考博客：http://t.csdn.cn/stiBa，感谢分享思路！）

代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int cmp(const void *a, const void *b){return *(int *)a - *(int *)b;//升序
}int main()
{int i,N,M,temp;scanf("%d %d",&N,&M);int num = N+M+1;//数字总个数int positive[num],negative[num];int lenp=0,lenn=0;long int sum = 0;for (i=0;i<num;i++){scanf("%d",&temp);if (temp<0)negative[lenn++] = temp;elsepositive[lenp++] = temp;}if (M==0)//全是加号,所有数字相加{for (i=0;i<lenp;i++)sum+=positive[i];for (i=0;i<lenn;i++)sum+=negative[i];}else //有负号{qsort(negative,lenn,sizeof(int),cmp);qsort(positive,lenp,sizeof(int),cmp);if (lenp==0)//全是负数时，最大值 = 最大的负数+其余所有负数的绝对值{sum = negative[--lenn];for (i=0;i<lenn;i++)sum+=abs(negative[i]);}else if (lenn==0)//全是正数时，最大值 = 其余所有数的和-最小的正数{sum-=positive[0];for (i=1;i<lenp;i++)sum+=positive[i];}else//有正数，也有负数，最大值 = 所有数的绝对值之和{for (i=0;i<lenp;i++)sum+=positive[i];for (i=0;i<lenn;i++)sum+=abs(negative[i]);}}printf("%ld",sum);return 0;
}