problem.txt (879B)
1 You are given an array of n integers a1,a2,…,an. 2 3 The value of an array is the sum of the maximums of each prefix of the array. More formally, the value of an array a is ∑ni=1max(a1,…,ai). For example, the value of the array [1,2,1] is max(1)+max(1,2)+max(1,2,1)=1+2+2=5. 4 5 You can choose two indices i and j and swap elements ai and aj; this operation can be applied at most one time. 6 7 Find the maximum possible value of the array a after at most one operation. 8 9 --- 10 11 so basically we have the following: 12 - an array where we can reorder two elements to make max(a_1,...) + max(a_1,...) ... where we are only summing the first n elements per step 13 - in this case we want to find the largest element of the array and swap it with the front element 14 - we then know the max across each of the n arrays is the largest element so the total sum is simply n*maxNum 15 16 --- 17