Divide array into smaller consecutive parts such that NEO value is maximal

Question

On this years Bubble Cup (finished) there was the problem NEO (which I couldn't solve), which asks

Given array with n integer elements. We divide it into several part (may be 1), each part is a consecutive of elements. The NEO value in that case is computed by: Sum of value of each part. Value of a part is sum all elements in this part multiple by its length.

Example: We have array: [ 2 3 -2 1 ]. If we divide it like: [2 3] [-2 1]. Then NEO = (2 + 3) * 2 + (-2 + 1) * 2 = 10 - 2 = 8.

The number of elements in array is smaller then 10^5 and the numbers are integers between -10^6 and 10^6

I've tried something like divide and conquer to constantly split array into two parts if it increases the maximal NEO number otherwise return the NEO of the whole array. But unfortunately the algorithm has worst case O(N^2) complexity (my implementation is below) so I'm wondering whether there is a better solution

EDIT: My algorithm (greedy) doesn't work, taking for example [1,2,-6,2,1] my algorithm returns the whole array while to get the maximal NEO value is to take parts [1,2],[-6],[2,1] which gives NEO value of (1+2)*2+(-6)+(1+2)*2=6

#include <iostream>
int maxInterval(long long int suma[],int first,int N)
{
    long long int max = -1000000000000000000LL; 
    long long int curr;
    if(first==N) return 0;
    int k;
    for(int i=first;i<N;i++)
    {
        if(first>0) curr = (suma[i]-suma[first-1])*(i-first+1)+(suma[N-1]-suma[i])*(N-1-i); // Split the array into elements from [first..i] and [i+1..N-1] store the corresponding NEO value
        else curr = suma[i]*(i-first+1)+(suma[N-1]-suma[i])*(N-1-i); // Same excpet that here first = 0 so suma[first-1] doesn't exist
        if(curr > max) max = curr,k=i; // find the maximal NEO value for splitting into two parts
    }
    if(k==N-1) return max; // If the max when we take the whole array then return the NEO value of the whole array
    else
    {
        return maxInterval(suma,first,k+1)+maxInterval(suma,k+1,N); // Split the 2 parts further if needed and return it's sum
    }
}
int main() {
    int T;
    std::cin >> T;
    for(int j=0;j<T;j++) // Iterate over all the test cases
    {
        int N;
        long long int NEO[100010]; // Values, could be long int but just to be safe
        long long int suma[100010]; // sum[i] = sum of NEO values from NEO[0] to NEO[i]
        long long int sum=0;
        int k;
        std::cin >> N;
        for(int i=0;i<N;i++)
        {
            std::cin >> NEO[i];
            sum+=NEO[i];
            suma[i] = sum;
        }
        std::cout << maxInterval(suma,0,N) << std::endl;
    }
    return 0;
}

Answer 1

This is not a complete solution but should provide some helpful direction.

1. Combining two groups that each have a positive sum (or one of the sums is non-negative) would always yield a bigger NEO than leaving them separate:

   m * a + n * b < (m + n) * (a + b) where a, b > 0 (or a > 0, b >= 0); m and n are subarray lengths

2. Combining a group with a negative sum with an entire group of non-negative numbers always yields a greater NEO than combining it with only part of the non-negative group. But excluding the group with the negative sum could yield an even greater NEO:

   [1, 1, 1, 1] [-2] => m * a + 1 * (-b)

   Now, imagine we gradually move the dividing line to the left, increasing the sum b is combined with. While the expression on the right is negative, the NEO for the left group keeps decreasing. But if the expression on the right gets positive, relying on our first assertion (see 1.), combining the two groups would always be greater than not.

3. Combining negative numbers alone in sequence will always yield a smaller NEO than leaving them separate:

   -a - b - c ... = -1 * (a + b + c ...)

   l * (-a - b - c ...) = -l * (a + b + c ...)

   -l * (a + b + c ...) < -1 * (a + b + c ...) where l > 1; a, b, c ... > 0

O(n^2) time, O(n) space JavaScript code:

function f(A){
  A.unshift(0);

  let negatives = [];
  let prefixes = new Array(A.length).fill(0);
  let m = new Array(A.length).fill(0);

  for (let i=1; i<A.length; i++){
    if (A[i] < 0)
      negatives.push(i);

    prefixes[i] = A[i] + prefixes[i - 1];
    m[i] = i * (A[i] + prefixes[i - 1]);

    for (let j=negatives.length-1; j>=0; j--){
      let negative = prefixes[negatives[j]] - prefixes[negatives[j] - 1];
      let prefix = (i - negatives[j]) * (prefixes[i] - prefixes[negatives[j]]);

      m[i] = Math.max(m[i], prefix + negative + m[negatives[j] - 1]);
    }
  }

  return m[m.length - 1];
}

console.log(f([1, 2, -5, 2, 1, 3, -4, 1, 2]));
console.log(f([1, 2, -4, 1]));
console.log(f([2, 3, -2, 1]));
console.log(f([-2, -3, -2, -1]));

Update

This blog provides that we can transform the dp queries from

dp_i = sum_i*i + max(for j < i) of ((dp_j + sum_j*j) + (-j*sum_i) + (-i*sumj))

to

dp_i = sum_i*i + max(for j < i) of (dp_j + sum_j*j, -j, -sum_j) ⋅ (1, sum_i, i)

which means we could then look at each iteration for an already seen vector that would generate the largest dot product with our current information. The math alluded to involves convex hull and farthest point query, which are beyond my reach to implement at this point but will make a study of.