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

Question

我试图弄清楚为什么以下解决方案对于 codility 网站中“Max Double Slice Sum”问题的单个性能测试用例失败: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;
    }
}

思路很简单:

• 问题可以改写为寻找 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;所以当我=1时；最大 S = 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%；一个失败的性能测试用例如下所示:

中等_范围-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 索引处结束)的所有切片的最大值。完整代码如下:

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;
    }
}