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

    07-25 21:04