我在Codility Lessons上偶然发现了这个问题,下面是描述:
给出一个由N个整数组成的非空零索引数组A。
一个三元组(X,Y,Z),使得0 ≤ X < Y < Z < N,称为双切片。
双切片(X,Y,Z)的和是A[X + 1] + A[X + 2] +…+ A[Y − 1] + A[Y + 1] + A[Y + 2] + ...+ A[Z − 1]。
例如,数组A使得:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
包含以下双切片示例:
双切片(0,3,6),和为2 + 6 + 4 + 5 = 17,
double slice(0,3,7),sum = 2 + 6 + 4 + 5 − 1 = 16,
double slice(3,4,5),sum为0。
目标是找到任何双切片的最大和。
写一个函数:
int solution(vector &A);
给定由N个整数组成的非空零索引数组A,返回任何双切片的最大和。
例如,给定:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
函数应该返回17,因为数组A的双切片的和都不大于17。
假设:
N是在[3..100,000]范围内的整数;数组A的每个元素都是[-10,000..10,000]范围内的整数。
复杂度:
时间复杂度为O(N);最坏情况下的空间复杂度是O(N),超出输入存储(不计算>输入参数所需的存储)。
可以修改输入数组的元素。
我已经读过关于计算MaxSum从索引i开始到索引i结束的算法,但我不知道为什么我的方法有时会产生不好的结果。这个想法是计算在索引i结束的MaxSum,省略范围0..i的最小值。下面是我的代码:
int solution(vector<int> &A) {
int n = A.size();
int end = 2;
int ret = 0;
int sum = 0;
int min = A[1];
while (end < n-1)
{
if (A[end] < min)
{
sum = max(0, sum + min);
ret = max(ret, sum);
min = A[end];
++end;
continue;
}
sum = max(0, sum + A[end]);
ret = max(ret, sum);
++end;
}
return ret;
}
如果你能帮我指出漏洞,我会很高兴的!
5条答案
按热度按时间hrirmatl1#
我的解决方案基于双向Kadane算法。更多详情请访问我的博客here。满分100分。
o8x7eapl2#
下面是我的代码:
实际的解决方案是
get_max_sum
函数(另外两个是蛮力解决方案和测试器函数,用于生成随机数组并比较蛮力和实际解决方案的输出,我仅将它们用于测试目的)。我的解决方案背后的想法是计算一个子数组中的最大和,该子数组开始于
i
之前的某个地方,结束于i - 1
,然后对足够数(分别为best_pref[i]
和best_suf[i]
)做同样的事情。之后,我只是迭代所有的i
并返回best_pref[i] + best_suf[i]
的最佳值。它正确工作,因为best_pref[y]
为固定的y
找到最好的x
,best_suf[y]
为固定的y
找到最好的z
,并且检查了y
的所有可能值。ax6ht2ek3#
uxhixvfz4#
Ruby100%
hc2pp10m5#
Java:一种替代方法