最大双片和密码O(1)空间复杂度失败性能测试用例
我在试图弄清楚为什么下面的解决方案对于密码网站中的“最大双片和”问题的单个性能测试用例失败：总和
还有另一种解决方案O(n)的空间复杂性，在这里更容易理解：最大双片和。但我只是想知道为什么这个O(1)解决方案不起作用。以下是实际代码：
import java.util.*;
class Solution {
public int solution(int[] A) {
long maxDS = 0;
long maxDSE = 0;
long maxS = A[1];
for(int i=2; i<A.length-1; ++i){
//end at i-index
maxDSE = Math.max(maxDSE+A[i], maxS);
maxDS = Math.max(maxDS, maxDSE);
maxS = Math.max(A[i], maxS + A[i]);
}
return (int)maxDS;
}
}这个想法很简单，如下：
- 该问题可以重新定义为求max(Ai+Ai+1+.+ Am )；1<=i<=m<=j<=n-2；而n= A.length；我们称Am是片内缺少的元素。
- maxSi将保留以当前索引i结尾的max片；换句话说，= max(At +.+ Ai)；而t< i；因此，当i=1；maxS = A1；注意，在解决方案中，我们不保留数组，而是在当前索引中保留最新的maxS (见上面的代码)。
- maxDSEi是以i结尾的所有双片的最大值；换句话说，= max ( at + at +1+.+Ai)--终点在Ai；maxDS是我们试图找到的双片和的最终最大值。
现在，我们只使用来自i=2的For -循环；-> i=A.length-2；对于每个索引i，我们注意到一些发现：
- 如果缺少的元素是Ai，那么maxDSEi = maxS一-一；
- 如果缺少的元素不是Ai ->，那么它必须位于A_1 -> Ai _1-> maxDSE = maxDSEi-1 + Ai；例如At +.+Ai- A我 with tso maxDSEi = Math.max(maxDSEi-1+Ai，maxSi-1)；maxDS = Math.max(maxDS，maxDSE)；最大值all maxDSE；maxSi = Math.max(Ai，maxSi-1+Ai)；
这样，maxDS将是最终的结果。
但奇怪的是，我只获得了92%的成绩；只有一个失败的性能测试用例，如下所示：
medium_range - 1000，…，1000
错误的答案得到499499预期的499500
有谁能告诉我，我的解决方案中的问题在哪里？谢谢!
回答 4
Stack Overflow用户
发布于 2015-02-21 01:52:20
好的，我在代码中发现了错误。好像我忘了一个角落的箱子。在计算DSEi时，在Ai缺少数字的情况下，当数组为空时，maxS应该包含这个情况。换句话说，maxS应计算为: maxSi = Math.max(0，Math.max(Ai+maxSi-1，Ai))；0为空子阵(结束于i-th)；Math.max(Ai+maxSi-1，Ai)是所有切片的最大值，至少有一个元素(结束于I-索引)。完整代码如下：
import java.util.*;
class Solution {
public int solution(int[] A) {
long maxDS = 0;
long maxDSE = 0;
long maxS = A[1];
for(int i=2; i<A.length-1; ++i){
maxDSE = Math.max(maxDSE+A[i], maxS);
maxDS = Math.max(maxDS, maxDSE);
maxS = Math.max(0, Math.max(A[i], maxS + A[i]));
}
return (int)maxDS;
}
}Stack Overflow用户
发布于 2016-02-23 22:05:00
似乎对于输入-11，-53，-4，38，76，80，您的解决方案不起作用。是的，它欺骗了所有的密码测试用例，但我也设法在其他问题上欺骗了所有的密码测试用例。
如果您不只是想欺骗盲从，而且还想提供一个很好的解决方案，我建议您创建一个循环和大量随机测试用例(元素和元素值的数量)，并创建一个您自己的测试方法(即使复杂度是二次的)，比较这两种方法的结果，然后分析不适合的当前随机输入。
Stack Overflow用户
发布于 2017-05-12 17:49:07
这是明确的解决办法。最好的方法是空间上使用Kanade O(N)和O(1)的算法。
public class DuplicateDetermineAlgorithm {
public static boolean isContainsDuplicate(int[] array) {
if (array == null) {
throw new IllegalArgumentException("Input array can not be null");
}
if (array.length < 2) {
return false;
}
for (int i = 0; i < array.length; i++) {
int pointer = convertToPositive(array[i]) - 1;
if (array[pointer] > 0) {
array[pointer] = changeSign(array[pointer]);
} else {
return true;
}
}
return false;
}
private static int convertToPositive(int value) {
return value < 0 ? changeSign(value) : value;
}
private static int changeSign(int value) {
return -1 * value;
}
}https://stackoverflow.com/questions/28631437
复制相似问题
腾讯云开发者
