链接：https://ac.nowcoder.com/acm/contest/96846/b 来源：牛客网 小 z 获得了一个长度为 𝑛 n 的序列 𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 a 1 ​ ,a 2 ​ ,…,a n ​ ，现在他希望在每相邻的两个数字之间插入 加号或乘号。 但是很不幸，年仅三岁的小 z 对加减乘除的运算顺序掌握的并不很好。在他的理解中，所有算式都是从左往右计算的。例如对于算式 1 + 2 × 3 + 4 1+2×3+4，小 z 会这么计算： 1 + 2 × 3 + 4 → 3 × 3 + 4 → 9 + 4 → 13 1+2×3+4→3×3+4→9+4→13 小 z 希望你告诉他，在他理解的计算规则下，这个式子通过合理地插入 加号或乘号，最大能达到的值会是多少呢？ 更进一步的，小 z 想知道：如果他可以重新排列这 𝑛 n 个数字，按照他理解的计算方法，这个式子最大结果又会是多少呢？ 小 z 的数学很差，于是他只好求助聪明的你，请你告诉他 原始数列的答案 和 重排后的答案 分别是多少？由于这个式子的结果可能会很大，因

此请你输出模 1 0 9 + 7 的值。 输入描述: 第一行一个整数 𝑛 n ( 1 ≤ 𝑛 ≤ 10 5 ) n（1≤n≤105）表示序列长度。 接下来一行 𝑛 n 个整数 𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 a 1 ​ ,a 2 ​ ,…,a n ​ ( − 1 0 6 ≤ 𝑎 𝑖 ≤ 1 0 6 ) (-10^6≤a_i≤10^6)表示序列。 输出描述: 输出答案 示例1 输入 2 1 2 输出 13 9 示例2 输入 3 1 1 2 输出 7 4 解题思路： 1. 首先，观察题目给出的规则，可以看到乘法的优先级高于加法，而加法是从左到右依次进行的。也就是说，在每一个加法操作之前必须要完成该加法操作的前一个乘法操作。 2. 因此，可以采用动态规划的方法来解决这个问题。 3. 设计两个数组 maxVal 和 minVal，其中 maxVal[i] 表示序列的前 i 个元素通过加号和乘号操作得到的最大值，minVal[i] 表示序列的前 i 个元素通过加号和乘号操作得到的最小值。 4. 递推关系为： - maxVal[i] = max(maxVal[i-1]*a[i], a[i])+maxVal[i-1] - minVal[i] = min(minVal[i-1]*a[i], a[i])+minVal[i-1] 5. 最终答案为 maxVal[n]。 6. 对于重新排列数字的问题，可以先将数组按照从大到小排列，然后再利用上述的动态规划方法求解。 [2024-11-23 17:43:39 | AI写代码神器 | 662点数解答]