Max Double Slice Sum codility O(1)空间复杂性失败性能测试用例

Question

我试图弄清楚为什么下面的解决方案在代码网站中针对"Max Double Slice Sum"问题的单个性能测试案例失败了:https://codility.com/demo/take-sample-test/max_double_slice_sum

还有另一种解决方案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(A [i] + A [i + 1] + ... + A [j] -A [m]); 1 <= I <= M <= j的<= N-2; 而n = A.length; 我们称切片中的A [m]缺少元素.
• maxS [i]将保持以当前索引i结束的最大切片; 换句话说,= max(A [t] + ... + A [i]); 而t <i; 所以当i = 1时; maxS = A [1]; 请注意,在解决方案中,我们不保留数组,而是保留当前索引的最新maxS(参见上面的代码).
• maxDSE [i]是在i处结束的所有双切片的最大值; 换句话说,= max(A [t] + A [t + 1] + ... + A [i] -A [m]) - 在A [i]处结束; maxDS是我们试图找到的双切片总和的最终最大值.

现在,我们只使用i = 2的for循环; - > i = A.length-2; 对于每个索引i,我们注意到一些发现:

1. 如果缺失的元素是A [i],则maxDSE [i] = maxS [i-1](在i-1 =>或A [t] + ... + A [i]处结束的所有切片的最大和 - A [i]);

2. 如果缺少的元素不是A [i] - >所以它必须在A [1] - > A [i-1] - > maxDSE = maxDSE [i-1] + A [i]的某处; 例如A [t] + ... + A [i] - A [m](不是A [i]必须是最后一个元素)与t

   所以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

有谁可以请教我解决方案中的问题在哪里？谢谢!

Answer 1

好的,我发现我的代码出错了.似乎我忘了一个角落的案例.当计算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;
    }
}