algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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