Slow Sums Algorithm

Question

Suppose we have a list of N numbers and repeat the following operation until we're left with only a single number: Choose any two consecutive numbers and replace them with their sum. Moreover, we associate a penalty with each operation equal to the value of the new number and call the penalty for the entire list as the sum of the penalties of each operation.

Note: Consecutive numbers means that their indices in the array are consecutive, not that their values are consecutive. For example, given the list [1, 2, 3, 4, 5], we could choose 2 and 3 for the first operation, which would transform the list into [1, 5, 4, 5] and incur a penalty of 5. The goal in this problem is to find the worst possible penalty for a given input.

Constraints: 1 ≤ N ≤ 10^6 1 ≤ Ai ≤ 10^7, where *Ai denotes the ith initial element of an array. The sum of values of N over all test cases will not exceed 5 * 10^6.

Example
arr = [4, 2, 1, 3]
output = 23
First, add 4 + 2 for a penalty of 6. Now the array is [6, 1, 3]
Add 6 + 1 for a penalty of 7. Now the array is [7, 3]
Add 7 + 3 for a penalty of 10. The penalties sum to 23.

int getTotalTime(int[] arr) {}

Answer 1

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;
}

Answer 2

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²).