1、问题
给定N个加号、M个减号以及N+M+1个整数A1,A2,A3... ,AN+M+1,小明想知道在所有由这N个加号、M个减号以及N+M+1个整数凑出的合法的后缀表达式中,结果最大的是哪一个?请你输出这个最大的结果。 例如使用1 2 3 + -.则“2 3 + 1 -"这个后缀表达式结果是4,是最大的。
2、方法
首先,根据题目的要求可知,所有的计算都是按照运算符号出现的顺序,从左往右进行的,而后缀表达式是将运算符号放在两数之后,然后,可以先确定减号的数量,如果m=0,就是将所有数相加,如果m>0,需要分成三类来讨论,当数据全为负数时,就是加上最大的数,减去剩下的数字,当数据全为正数时,就是减去最小的数,加上剩余的数,当数据有正数也有负数时,最后的最大值就等于所有数的绝对值之和。
3、实验结果与讨论
通过实验、实践等证明提出的方法是有效的,是能够解决开头提出的问题。
代码清单 1
n,m=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
if m==0:
result=sum(nums)
else:
if nums[0]>0:
result=sum(nums[1:len(nums)])-nums[0]
elif nums[-1]<0:
result=sum(nums[0:len(nums)-1])*(-1)+nums[-1]
else:
absnums=[abs(x) for x in nums]
result=sum(absnums)
print(result)
4、结语
针对后缀表达式问题,提出先分析再分类讨论方法,通过实验,证明该方法是有效的,当然也会存在其他的解决方法,但是对于题目的解题思路,不仅能用于解决题目,更能在平常做事的解决思路。
稿件来源:深度学习与文旅应用实验室(DLETA)
作者:彭淮
主编:欧洋