kin*_*gW3 7 c++ arrays algorithm
给定具有n个整数元素的数组.我们将它分成几个部分(可能是1),每个部分是连续的元素.在这种情况下的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;
}
这不是一个完整的解决方案，但应该提供一些有用的方向。
\n\n将两个总和为正数（或其中一个和为非负数）的组组合在一起总是会产生比将它们分开更大的 NEO：
\n\nm * a + n * b < (m + n) * (a + b) where a, b > 0 (or a > 0, b >= 0); m and n are subarray lengths
将具有负和的群与整个非负数群组合总是比仅与部分非负数组合产生更大的 NEO。但排除负总和的组可能会产生更大的 NEO：
\n\n[1, 1, 1, 1] [-2] => m * a + 1 * (-b)
现在，想象我们逐渐将分界线向左移动，增加 b 的总和。虽然右侧的表达式为负，但左侧组的 NEO 不断减小。但是，如果右侧的表达式为正，则根据我们的第一个断言（参见 1.），将两组组合起来总是大于不组合。
按顺序单独组合负数总是会产生比将它们分开的更小的 NEO：
\n\n-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
\nO(n^2)时间，O(n)空间 JavaScript 代码：
function f(A){\r\n A.unshift(0);\r\n\r\n let negatives = [];\r\n let prefixes = new Array(A.length).fill(0);\r\n let m = new Array(A.length).fill(0);\r\n\r\n for (let i=1; i<A.length; i++){\r\n if (A[i] < 0)\r\n negatives.push(i);\r\n\r\n prefixes[i] = A[i] + prefixes[i - 1];\r\n m[i] = i * (A[i] + prefixes[i - 1]);\r\n\r\n for (let j=negatives.length-1; j>=0; j--){\r\n let negative = prefixes[negatives[j]] - prefixes[negatives[j] - 1];\r\n let prefix = (i - negatives[j]) * (prefixes[i] - prefixes[negatives[j]]);\r\n\r\n m[i] = Math.max(m[i], prefix + negative + m[negatives[j] - 1]);\r\n }\r\n }\r\n\r\n return m[m.length - 1];\r\n}\r\n\r\nconsole.log(f([1, 2, -5, 2, 1, 3, -4, 1, 2]));\r\nconsole.log(f([1, 2, -4, 1]));\r\nconsole.log(f([2, 3, -2, 1]));\r\nconsole.log(f([-2, -3, -2, -1]));这个博客提供了我们可以将 dp 查询从
\n\ndp_i\xe2\x80\x89=\xe2\x80\x89sum_i*i\xe2\x80\x89+\xe2\x80\x89max(for j\xe2\x80\x89<\xe2\x80\x89i) of ((dp_j\xe2\x80\x89+\xe2\x80\x89sum_j*j)\xe2\x80\x89+\xe2\x80\x89(-j*sum_i)\xe2\x80\x89+\xe2\x80\x89(-i*sumj))\n到
\n\ndp_i = sum_i*i + max(for j < i) of (dp_j + sum_j*j, -j, -sum_j) \xe2\x8b\x85 (1, sum_i, i)\n这意味着我们可以在每次迭代中查看已经看到的向量，该向量将与我们当前的信息生成最大的点积。提到的数学涉及凸包和最远点查询，这些在我目前无法实现，但会进行研究。
\n