阵元连续和的最优解
阵元连续和的最优解
提问于 2018-08-26 21:50:23
谁能为下面的问题提出最优的解决方案？给定一个正/负整数数组，返回最大“特殊和”。给定一个数组A，每个数组索引处的“特殊和”定义如下。
S[i] = S[i] + (S[i+1] + S[i+2]) + (S[i+3] + S[i+4] + S[i+5]) + (S[i+6] + S[i+7] + S[i+8] + S[i+9]) + .....也就是说，对于索引i处的元素，我们添加下一个2个元素，然后是下一个3，然后是下一个4，直到我们有了数组中可用的这些数字子集。
例如；数组结果3 1 2 5 -5 =>：8解释：
S[0] = 1+(3+1)+(2+5-5)=7;
s[1] = 3+(1+2)=6;
S[3] = 1+(2+5)=8;
S[4] = 2+(5-5)=2;
S[5] = 5; S[6] = -5;当S3为max时，这就是结果。这个问题可以用3个循环来解决，有没有最好的解决方法呢？
回答 1
Stack Overflow用户
发布于 2018-11-30 03:32:42
第1部分
给定长度为N的数组S，请考虑以下顺序：
R[i] = S[i+1] + s[i+2] + s[i+3] + ... + s[N-1] + s[N]
R[i+1] = S[i+2] + s[i+3] + ... + s[N-1] + S[N]
...
R[N-1] = S[n]这意味着Rk = Sk + Rk+1
循环nr 1：
from N to 0 do:
R[k] = s[k]
if R[k+1] exists do
R[k] = R[k] + R[k+1]例如，如果N=9 sum由下图中的x‘is反映：
123456789
S[0] xxxxxxxxx
S[1] xxxxxxxx
S[2] xxxxxxx
S[3] xxxxxx
S[4] xxxxx
S[5] xxxx
S[6] xxx
S[7] xx
S[8] x 第2部分
我们假设每行相加的元素数必须是三角数(序列1+2+3的元素...，有效元素是1,3,6,10，...)
为了可视化这一点，让我们以我们的示例为例：
123456789
S[0] xxxxxx
S[1] xxxxxx
S[2] xxxxxx
S[3] xxxxxx
S[4] xxx
S[5] xxx
S[6] xxx
S[7] x
S[8] x 请注意，在每一行(带有索引i)中，末尾可能有间隙。当数字N-i不是三角形时，就会出现间隙。
例如，在索引i=0：N-i = 9中，小于9的最大三角形数是6
要获得适合某个数字的最小三角形数，请使用下面的公式：
function closest_triangle(n)
((sqrt(8*n+1) -1) / 2).floor
end第2部分现在简单地遍历每个Ri，其中i=0...N和substract不需要的部分：
for i in 0..N
for j in 0..closest_triangle(N-i)
R[i] = R[i] - S[i + j + 1]
end
end当然，你可以存储部分减法和，因为这些会被重复。例如，如果N=21：
xxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxx
xxx
xxx
x
x 因此，这将简化计算(存储最后一些数字的和)。
现在谈到复杂性：
在第1部分中，我们创建大小为N的数组，并进行N个基本操作。
在第2部分中，如果将使用memoization (存储最后N个元素的总和)，那么我们也将有N个基本操作
这样，算法的复杂度将达到O(n)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52026892
复制相关文章
相似问题
腾讯云开发者
