将数组分成较小的连续部分，使得NEO值最大。

Question

今年的Bubble Cup比赛已经结束，有一个问题NEO我没能解决。这个问题要求给定一个包含n个整数元素的数组，将其分成若干部分（可以只有一部分），每一部分都是连续的元素。在这种情况下，NEO值的计算方式为：每一部分的值之和。一部分的值是该部分中所有元素之和乘以其长度。

例如：我们有一个数组：[ 2 3 -2 1 ]。如果我们将其划分为：[2 3] [-2 1]。则NEO = (2 + 3) * 2 + (-2 + 1) * 2 = 10 - 2 = 8。

数组中的元素数量小于10^5，数字是介于-10^6和10^6之间的整数。

我尝试过类似分治的方法，如果将数组不断分成两部分可以增加最大NEO数字，则执行此操作，否则返回整个数组的NEO。但不幸的是，该算法的最坏情况复杂度为O(N^2)（以下是我的实现），因此我想知道是否有更好的解决方案。

编辑：我的贪心算法不起作用，例如取[1,2,-6,2,1]，我的算法返回整个数组，而获取最大NEO值的方法是取[1,2],[-6],[2,1]部分，从而得到NEO值为(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;
}

- kingW3

---

仅获得O(n^2)的结果已经相当不错了：暴力算法是O(n 2^n)，来自于_n_的组合数量。 - Davis Herring

@PhamTrung 我的代码中有一些错误（如使用0代替first等），这使得复杂度呈指数级增长。在修复了这些错误后，我尝试了输入1 10000，然后是10000个数字-1的算法。此后，数组被分成了10000个长度为1的部分，进入递归19999次，并且计算总迭代次数接近150000，看起来相当稳定。虽然我认为我的算法并不适用于每个输出。 - kingW3

啊，我看到你的方法是贪心的，通过选择最大的部分贪婪地分割数组。也许使用区间树可以帮助更快地找到最大的部分，这将使你的程序复杂度降为O(nlogn)，但我仍然不确定正确性。 - Pham Trung

@Yola，我刚刚发现了一个反例。如果我取1 2 -6 2 1，我的算法会选择整个数组，这将得到0*6 = 0，而最优解是[1,2]，[-6]，[2,1] = (1+2)*2+(-6)+(2+1)*2=6。看来我需要重新开始设计算法了:P - kingW3

谢谢更新。我尝试了动态编程方法，但它需要太多的内存并且无法满足时间限制。 - Yola

Answer 1

这不是完整的解决方案，但应该提供了一些有用的指导。

1. 合并两个每个都有正和（或其中一个和为非负数）的组将总是产生比分开时更大的NEO：

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

2. 将一个负和组与一个全是非负数的组合并总是会产生比仅与非负数部分组合并更大的NEO。但是排除具有负总和的组可能会产生更大的NEO：

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

   现在，想象我们逐渐将分界线向左移动，增加与之组合的和b。当右侧表达式为负数时，左侧组的NEO保持减少。但是如果右侧表达式变为正数，则根据我们的第一个断言（见1），合并两个组总是优于不合并。

3. 仅按顺序合并负数将总是产生比分开时更小的NEO：

   -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) 时间，O(n) 空间的 JavaScript 代码：

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]));

更新

这篇博客 提供了一种方法，可以将 dp 查询从原来的形式转换为：

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

为了

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

这意味着我们可以在每个迭代中寻找已经出现的向量，这些向量可以生成最大的点积并提供当前信息。所提到的数学涉及凸包和最远点查询，这些超出了我的实现范围，但我将进行研究。

- גלעד ברקן

---

谢谢提供的链接，非常有帮助。如果我成功实现了自己的解决方案，我会在这里发布答案。 - kingW3

@kingW3 是的，计算几何与这些数字查询的关系非常有趣。我正在尝试自己进行可视化。(顺便说一句，如果你遇到困难，请注意用户dacin21在那篇博客中发布了完整的代码 :) - גלעד ברקן