最大双切片总和

algorithm java

2022-09-02 11:32:29

最近，我试图解决codility中的最大双切片总和问题，这是max切片问题的变体。我的解决方案是寻找一个切片，当其最小值被取出时，它具有最大值。所以我实现了最大切片，但在当前切片上取出了最小数量。

我的分数是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;
    }
}

答案 1

如果我正确地理解了这个问题，你想要计算缺少一个元素的最大和子数组。

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

 1 1 0 10 -100 10 0

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

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

对于每个指数，使用Kadane的正向算法计算值。max_sum_ending_at[i]
对于每个指数，使用Kadane的反向算法计算值。max_sum_starting_from[i]
同时迭代这些数组，并选择最大值为

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

答案 2

你好，这个实现有100分

int i,n ;

n = A.size();

if (3==n) return 0;

vector<int>  max_sum_end(n,0);
vector<int>  max_sum_start(n,0);

for (i=1; i< (n-1); i++) // i=0 and i=n-1 are not used because x=0,z=n-1
{
  max_sum_end[i]   = max ( 0 , max_sum_end[i-1] + A[i]  ); 
}

for (i=n-2; i > 0; i--) // i=0 and i=n-1 are not used because x=0,z=n-1
{
   max_sum_start[i]   = max ( 0 , max_sum_start[i+1] + A[i]  ); 
}  

int maxvalue,temp;
maxvalue = 0;

for (i=1; i< (n-1); i++)
{
 temp = max_sum_end[i-1]  + max_sum_start[i+1];
 if ( temp >  maxvalue) maxvalue=temp;
}

return maxvalue ;