java - 最大双切片和

Question

最近，我尝试解决 codility 中的 Max Double Slice Sum 问题，它是最大切片问题的变体。我的解决方案是在取出最小值时寻找具有最大值的切片。所以我实现了max slice，但是在当前slice上取出了最小的数。

我的分数是 61 分(满分 100 分)，因为它在一些测试中失败了，主要是对数组的测试，包括负数和位置数。

你能帮我弄清楚代码失败的原因，或者是否有更好的解决方案？

问题如下:

A non-empty zero-indexed array A consisting of N integers is given.
A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.
The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1]+ A[Y + 1] + A[Y + 2] + ... + A[Z − 1].
For example, array A such that:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
contains the following example double slices:
 double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
 double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
 double slice (3, 4, 5), sum is 0.
The goal is to find the maximal sum of any double slice.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers, returns the maximal sum of any double slice.
For example, given:
 A[0] = 3
 A[1] = 2
 A[2] = 6
 A[3] = -1
 A[4] = 4
 A[5] = 5
 A[6] = -1
 A[7] = 2
the function should return 17, because no double slice of array A has a sum of greater than 17.
Assume that:
 N is an integer within the range [3..100,000];
 each element of array A is an integer within the range [−10,000..10,000].
Complexity:
 expected worst-case time complexity is O(N);
 expected worst-case space complexity is O(N), beyond input storage (not counting the    storage required for input arguments).
Elements of input arrays can be modified.
Copyright 2009–2013 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

而我的代码如下:

public class Solution {
    public int solution(int[] A) {
        int currentSliceTotal=0; 
        Integer currentMin=null, SliceTotalBeforeMin =0;
        int maxSliceTotal= Integer.MIN_VALUE;
        for(int i= 1; i<A.length-1; i++){
            if( currentMin==null || A[i] < currentMin ){
                if(currentMin!=null ){
                    if(SliceTotalBeforeMin+currentMin <0){
                        currentSliceTotal-=SliceTotalBeforeMin;
                    } else {
                        currentSliceTotal += currentMin;
                    }
                }                
                currentMin = A[i];
                SliceTotalBeforeMin  =currentSliceTotal;

                if( SliceTotalBeforeMin<0){
                    SliceTotalBeforeMin = 0;
                    currentMin = null;
                    currentSliceTotal = 0;
                }
            } else {
                currentSliceTotal+= A[i];
            }

            maxSliceTotal = Math.max(maxSliceTotal, currentSliceTotal);
        }

        return maxSliceTotal;
    }
}

Answer 1

如果我没理解错的话，你想计算缺一个元素的子数组的最大和。

您的算法不适用于以下情况:

 1 1 0 10 -100 10 0

在上述情况下，您的算法应将 1, 1, 0, 10 识别为子数组的最大和并省略 0 以给出 12 作为输出。但是，在省略 -100 之后，您可以将 1, 1, 0, 10, -100, 10 作为答案。

您可以使用 Kadane 算法的修改形式来计算在每个索引处结束的 MAX Sum 子数组。

1. 对于每个索引，使用正向的 Kadane 算法计算 max_sum_ending_at[i] 值。
2. 对于每个索引，使用 Kadane 算法反向计算 max_sum_starting_from[i] 值。

3. 同时迭代这些数组并选择具有最大值的'Y'

   max_sum_ending_at[Y-1] + max_sum_starting_from[Y+1]