我正在尝试找出为什么以下解决方案未能在codility网站上针对“最大双倍切片总和”问题的单个性能测试用例失败的原因:https://codility.com/demo/take-sample-test/max_double_slice_sum
还有另一种O(n)空间复杂度的解决方案Max double slice sum,在这里更容易理解。但是我只是想知道为什么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;
}
}
这个想法很简单,如下所示:
现在,我们仅从i = 2开始使用for循环; -> i = A.length-2;对于每个索引i,我们注意到一些发现:
以i-1 =>或A [t] + ... + A [i]-A [i]结尾的所有切片;
因此,maxDSE [i] = Math.max(maxDSE [i-1] + A [i],maxS [i-1]);
maxDS = Math.max(maxDS,maxDSE);全部maxDSE的最大数量;
和maxS [i] = Math.max(A [i],maxS [i-1] + A [i]);
这样,maxDS将是最终结果。
但奇怪的是,我只能得到92%;有一个失败的性能测试用例,如下所示:
medium_range
-1000,...,1000
错误的答案
得到499499预期499500
任何人都可以启发我解决方案的问题吗?谢谢!
最佳答案
好的,我发现了我的代码错误。似乎我忘了一个极端的案例。在计算DSE [i]时,如果A [i]缺少数字,则maxS应包含数组为空的情况。换句话说,maxS应计算为:
maxS [i] = Math.max(0,Math.max(A [i] + maxS [i-1],A [i])); 0表示空子数组(第i个结束); Math.max(A [i] + maxS [i-1],A [i])是所有至少包含一个元素的切片的最大值(以i-index结尾)。完整的代码如下:
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;
}
}