Max double slice sum

Question

Recently, I tried to solve the Max Double Slice Sum problem in codility which is a variant of max slice problem. My Solution was to look for a slice that has maximum value when its minimum value is taken out. So I implemented max slice, but on the current slice took out the minimum number.

My score was 61 of 100 as it failed during some of the tests, mainly the tests on array including both negative and position numbers.

Could you help me to figure out why the code failed or if there is a better solution for the problem?

The problem is as follows:

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.

And my code is as follows:

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

If I have understood the problem correctly, you want to calculate the maximum sum subarray with one element missing.

Your algorithm shall not work for the following case:

 1 1 0 10 -100 10 0

In the above case, your algorithm shall identify 1, 1, 0, 10 as the maximum sum sub array and leave out 0 to give 12 as the output. However, you can have 1, 1, 0, 10, -100, 10 as the answer after leaving out -100.

You can use a modified form of Kadane's algorithm that calculates the MAX Sum subarray ending at each index.

1. For each index, calculate the max_sum_ending_at[i] value by using Kadane's algorithm in forward direction.
2. For each index, calculate the max_sum_starting_from[i] value by using Kadane's algorithm in reverse direction.

3. Iterate these arrays simultaneously and choose the 'Y' that has the maximum value of

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

Answer 2

Hello this implementacion has 100 score

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 ;