题目：Array Covering

给定长度为 𝑛 n 的数组 𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 a 1 ​ ,a 2 ​ ,…,a n ​ ，其中第 𝑖 i 个数的值为 𝑎 𝑖 a i ​ 。

小苯希望数组中所有数字的总和尽可能大，为此他可以做任意次如下操作： ∙   ∙选择一对下标 𝑙 , 𝑟 ( 1 ≦ 𝑙 < 𝑟 ≤ 𝑛 ) l,r(1≦l<r≤n)，接着将 ( 𝑙 , 𝑟 ) (l,r) 区间（注意是开区间）内的所有数都变为区间端点值的较大者。 形式化地，对所有 𝑗 ( 𝑙 < 𝑗 < 𝑟 ) j(l<j<r)，均执行： 𝑎 𝑗 :

max ⁡ ( 𝑎 𝑙 , 𝑎 𝑟 ) a j ​ :=max(a l ​ ,a r ​ )（其中 :

:= 表示赋值操作）。

你的任务就是求出数组总和的最大值。

思路：

每次操作选择区间 (l, r)，将开区间内的所有数变为 max(a[l], a[r])。 这个操作的本质是：用区间两端点的较大值 “覆盖” 中间的所有数。 多次操作后，数组的最终状态可以理解为：所有数最终都被替换成了数组中某些端点的最大值。 要让总和最大，最优策略是：让数组中尽可能多的数变成整个数组的全局最大值 M。 2. 正确结论 数组的第一个元素 a[1] 和最后一个元素 a[n] 永远无法被任何操作改变，因为它们永远是区间的端点，不会被覆盖。 中间的 n-2 个元素，都可以通过操作变成全局最大值 M。 因此，数组总和的最大值为： ans=a[1]+a[n]+M×(n−2)

代码：

#include <bits/stdc++.h> using namespace std;

int main() { int t,k; long long ans; cin >> t; while (t--) { long long n,max1=INT_MIN; cin >> n; long long num[n+5]; for (int i = 1; i <= n; i++) { cin >> num[i]; if(max1<num[i]){ max1=num[i]; k=i; } } if(k==1){ ans=max1*(n-1)+num[n]; } else if(k==n){ ans=num[1]+max1*(n-1); } else{ ans=num[1]+num[n]+max1*(n-2); } cout<<ans<<endl; } }