给定具有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,1]我的算法返回整个数组,而得到最大的NEO值是取部分[1,2],[ – ],[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,N) << std::endl;
}
return 0;
}
解决方法
>将两个组合在一起,每个组都有一个正数(或其中一个总和是非负数)总会产生一个更大的NEO,而不是将它们分开：
m * a n * b< (m n)*(a b)其中a,b> 0(或a> 0,b> = 0); m和n是子阵列长度
>将具有负和的组与整组非负数组合,总是产生比仅与非负组的一部分组合的更大的NEO.但排除负数的组可以产生更大的NEO：
[1,1,1] [-2] => m * a 1 *( – b)
现在,想象一下我们逐渐将分界线向左移动,增加总和b与之相结合.虽然右侧的表达式为负,但左侧组的NEO持续下降.但是如果右边的表达式得到肯定,依赖于我们的第一个断言(见1.),将两个组合在一起总是大于.
>按顺序单独组合负数将始终产生比将它们分开的更小的NEO：
-a – b – c … = -1 *(a b c ……)
l *( – a – b – c …)= – l *(a b c …)
-l *(a b c …)< -1 *(a b c ...)其中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,-5,3,-4,2]));
console.log(f([1,1]));
console.log(f([2,-2,1]));
console.log(f([-2,-3,-1]));
更新
This blog规定我们可以转换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)
这意味着我们可以查看已经看到的向量的每次迭代,该向量将使用我们当前的信息生成最大的点积.数学提到涉及凸壳和最远点查询,这是我无法实现的,但将进行研究.