Slow Sums Algorithm

Another Javascript solution that covers the given test cases

function getTotalTime(arr) {
  arr.sort();
  var sum = arr[arr.length-1];
  var penalty = 0;
  for(let i=arr.length-2; i>=0; i-- ) {
    sum +=arr[i];
    penalty += sum;
  }
  return penalty;
}

This is a greedy problem. The key behind it is to notice that we have to always follow the biggest sum possible in each iteration. In your case [4, 2, 1, 3], the first biggest sum is 6, then 7 and then 10.

The problem comes when the biggest sum appears multiple times, for example [5, 3, 7, 1], then you have to choose if it's better to start with [5, 3] or [7, 1].

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

int n = 6;                       //array size
int a[] = {2, 1, 7, 1, 5, 3};    //array

vector<pair<int, int>> v;        //positions we will analyse

void analyse(){                  //this method gets the positions with biggest sum
    int sum = 0;
    for(int i = 1; i < n; i++) sum = max(sum, a[i - 1] + a[i]);
    for(int i = 1; i < n; i++) if(a[i - 1] + a[i] == sum) v.push_back(make_pair(i - 1, i));
}

int evaluate_penalty(int i, int j){   //given a position, this method finds
    int l = i, r = j;                 //the biggest penalty starting there
    int penalty = a[i] + a[j];
    int val = penalty;
    while(i != 0 || j != n - 1){
        if(l > 0 && r < n - 1) {
            if(a[l - 1] > a[r + 1]) l--;
            else r++;
        }
        else if(l > 0) l--;
        else r++;

        val += (l != i ? a[l] : 0) + (r != j ? a[r] : 0);
        penalty += val;
        i = l; j = r;
    }
    return penalty;
}

int max_penalty(){            //this method finds the biggest penalty
    v.clear();                //within all the possible starting positions.
    analyse();
    int maxPenalty = 0;
    for(int i = 0; i < v.size(); i++){
        maxPenalty = max(maxPenalty, evaluate_penalty(v[i].first, v[i].second));
    }
    return maxPenalty;
}

int main(){
    cout<<max_penalty()<<endl;
    return 0;
}

The complexity is O(n²), BUT in most of the cases, it will be O(n). Given that the biggest sum between two consecutive numbers is s, the complexity relies on how many pairs of consecutive numbers sum s. If there is only one (like in your example [4, 2, 1, 3], it will finish in one iteration, hence O(n). If the array is something like [1, 1, 1, 1, 1, ..., 1], it will take O(n²).

I have solved it like this but not sure if it's optimal or not

static int getTotalTime(int[] arr) {
        List<Integer> output = new ArrayList<>();
        Arrays.stream(arr).forEach(output::add);
        if (output.size() < 3) {
            return output.stream().reduce((a, b) -> a + b).get();
        }

        int sum = 0;
        List<Integer> max1 = new ArrayList<>();
        max1.add(0);
        for (int i = 2; i < output.size(); i++) {
            if (output.get(i) + output.get(i - 1) > output.get(max1.get(0)) + output.get(max1.get(0) + 1)) {
                max1 = new ArrayList<>();
                max1.add(i - 1);
            }else if (output.get(i) + output.get(i - 1) == output.get(max1.get(0)) + output.get(max1.get(0) + 1)) {
                max1.add(i - 1);
            }
        }

        sum = sum + output.get(max1.get(0)) + output.get(max1.get(0) + 1);

        List newList = new ArrayList(output);
        newList.set(max1.get(0), output.get(max1.get(0)) + output.get(max1.get(0) + 1));
        newList.remove(max1.get(0) + 1);

        int remainingSum = getTotalTime(newList);

        for (int i = 1; i < max1.size(); i++) {
            newList = new ArrayList(output);
            newList.set(max1.get(i), output.get(max1.get(i)) + output.get(max1.get(i) + 1));
            newList.remove(max1.get(i) + 1);
            int nextRemainingSum = getTotalTime(newList);
            if (nextRemainingSum > remainingSum) {
                remainingSum = nextRemainingSum;
            }
        }

        sum += remainingSum;

        return sum;
    }

    static int getTotalTime(List<Integer> output) {
        int sum = 0;
        while (output.size() > 2) {
            int max1 = 0;
            for (int i = 2; i < output.size(); i++) {
                if (output.get(i) + output.get(i - 1) > output.get(max1) + output.get(max1 + 1)) {
                    max1 = i - 1;
                }
            }
            sum += output.get(max1) + output.get(max1 + 1);
            output.set(max1, output.get(max1) + output.get(max1 + 1));
            output.remove(max1 + 1);
        }

        return sum + output.stream().reduce((a, b) -> a + b).get();

    }

Here's an optimized solution in Javascript including a couple of test cases. The key principle is that the highest penalty can be obtained in each step by adding the two largest elements in the array.

//Begin Solution
function getTotalTime(arr) {
    function getTotal(a){
      if(a.length==2)
        return a[0]+a[1]
      else{
        const penalty = a[a.length-1]+a[a.length-2]
        return penalty+getTotal([...a.slice(0,a.length-2),penalty])
      }
          
    }
  return getTotal(arr.slice(0,arr.length).sort((a,b)=>a-b))
}
 //End Solution

  // These are the tests we use to determine if the solution is correct.

  function printInteger(n) {
    var out = '[' + n + ']';
    return out;
  }
  
  var test_case_number = 1;
  
  function check(expected, output) {
    var result = (expected == output);
    var rightTick = "\u2713";
    var wrongTick = "\u2717";
    if (result) {
      var out = rightTick + ' Test #' + test_case_number;
      console.log(out);
    }
    else {
      var out = '';
      out += wrongTick + ' Test #' + test_case_number + ': Expected ';
      out += printInteger(expected);
      out += ' Your output: ';
      out += printInteger(output);
      console.log(out);
    }
    test_case_number++;
  }
  
  var arr_1 = [4, 2, 1, 3];
  var expected_1 = 26;
  var output_1 = getTotalTime(arr_1);
  check(expected_1, output_1);
  
  var arr_2 = [2, 3, 9, 8, 4];
  var expected_2 = 88;
  var output_2 = getTotalTime(arr_2);
  check(expected_2, output_2);

  

There is better and simple solution for this problem using MaxHeap.

int getTotalPenalty (int[] arr) {
    PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
    for(int i = 0; i < arr.length; i++) {
        q.add(arr[i]);
    }
    int totalP = 0;
    while(q.size() > 1) {
        int penality =  q.poll() + q.poll();
        totalP = totalP + penality;
        q.add(penality);
    }
    return totalP;
}