牛客网难题：小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. 对于重新排列数字的问题，可以先将数组按照从大到小排列，然后再利用上述的动态规划方法求解。 ######[AI写代码神器 | 662点数解答 | 2024-11-23 17:43:39]