ARC174A - A Multiply

📘 题目描述

给定一个长度为 $N$ 的整数数组 $A = (A_1, A_2, \dots, A_N)$ 和一个整数 $C$。

你可以选择 至多一次 操作：

• 选择任意区间 $[l, r]$（满足 $1 \le l \le r \le N$），将区间内的所有元素乘以 $C$。

请你输出操作后，数组 $A$ 所有元素和的最大可能值。

📥 输入格式

N C
A\_1 A\_2 A\_3 ... A\_N

$1 \le N \le 3 \times 10^5$ $-10^6 \le A_i, C \le 10^6$

📤 输出格式

输出一个整数，表示最大可能的数组和。

💡 样例

🎯 样例输入 1

5 2
-10 10 20 30 -20

✅ 样例输出 1

90

🎯 样例输入 2

5 1000000
-1 -2 -3 -4 -5

✅ 样例输出 2

-15

🎯 样例输入 3

9 -1
-9 9 -8 2 -4 4 -3 5 -3

✅ 样例输出 3

13

🧠 样例解释

• 样例 1：操作区间为 $[2, 4]$，将 10, 20, 30 变为 20, 40, 60。新数组为：[-10, 20, 40, 60, -20]，总和为 $90$，是最大值。
• 样例 2：所有数都是负数，且 $C$ 很大，操作会使负值更负。最优解是不进行任何操作。
• 样例 3：选择合适的区间并乘以负数后，可以抵消原来的负数，得到更大的总和。

🔍 提示

• 枚举子段并计算 $(C - 1) \times \text{sum}$ 对总和的影响，可以转化为 最大子段和问题（Kadane 算法）。
• 操作的本质是：在原总和的基础上加上 $(C - 1) \times \text{某个子段和}$，因此关键在于找出该乘积影响最大的区间。