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

我正在尝试找出为什么以下解决方案未能在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;
    }
}

这个想法很简单，如下所示:

问题可以通过找到max(A [i] + A [i + 1] + ... + A [j] -A [m])来解决。 1

maxS [i]将保留在当前索引i处结束的max slice；换句话说，= max(A [t] + ... + A [i]);当t

maxDSE [i]是在i处结束的所有double slice的max；换句话说，= max(A [t] + A [t + 1] + ... + A [i] -A [m])-在A [i]处结束； maxDS是我们尝试查找的双切片和的最终最大值。

现在，我们仅从i = 2开始使用for循环； -> i = A.length-2;对于每个索引i，我们注意到一些发现:

如果缺少的元素是A [i]，则maxDSE [i] = maxS [i-1](
以i-1 =>或A [t] + ... + A [i]-A [i]结尾的所有切片；

如果缺少的元素不是A [i]->，那么它必须在A [1]-> A [i-1]-> maxDSE = maxDSE [i-1] + A [i]的某个位置；例如A [t] + ... + A [i]-A [m](不是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;
    }
}