gpt4 book ai didi

c++ - 将数组分成较小的连续部分,使 NEO 值最大

转载 作者:可可西里 更新时间:2023-11-01 18:38:13 29 4
gpt4 key购买 nike

关于这一年Bubble Cup (完)有问题NEO (我无法解决),它要求

给定一个包含 n 个整数元素的数组。我们把它分成几个部分(可能是1个),每个部分都是一个连续的元素。这种情况下的 NEO 值(value)是通过以下方式计算的: 每个部分的值(value)总和。一个部分的值是该部分中所有元素的总和乘以它的长度。

示例:我们有数组:[ 2 3 -2 1 ]。如果我们像这样划分它:[2 3] [-2 1]。那么 NEO = (2 + 3) * 2 + (-2 + 1) * 2 = 10 - 2 = 8。

数组中的元素个数小于10^5,并且数字是-10^610^6之间的整数

我已经尝试过分而治之之类的方法,如果它增加了最大 NEO 数量,则不断地将数组分成两部分,否则返回整个数组的 NEO。但不幸的是,该算法具有最坏情况 O(N^2) 复杂度(我的实现如下)所以我想知道是否有更好的解决方案

编辑:我的算法(贪心)不起作用,例如 [1,2,-6,2,1] 我的算法返回整个数组,同时获得最大的 NEO 值是采取部分 [1,2],[-6],[2,1] 给出 (1+2)*2+(-6)+(1 的 NEO 值+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;
}

最佳答案

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

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

更新

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)

这意味着我们可以在每次迭代中查看一个已经看到的 vector ,该 vector 将与我们当前的信息生成最大的点积。提到的数学涉及到凸包和最远点查询,这超出了我在这一点上实现的能力,但会研究一下。

关于c++ - 将数组分成较小的连续部分,使 NEO 值最大,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50727167/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com