'Max double slice sum

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;
    }
}
javaalgorithm


Solution 1:[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]

Solution 2:[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 ;

Solution 3:[3]

This is a Java 100/100 Solution: https://codility.com/demo/results/demoVUMMR9-JH3/

class Solution {
    public int solution(int[] A) {        
        int[] maxStartingHere = new int[A.length];
        int[] maxEndingHere = new int[A.length];
        int maxSum = 0, len = A.length;

        for(int i = len - 2; i > 0; --i ) {            
            maxSum = Math.max(0, A[i] + maxSum);
            maxStartingHere[i] = maxSum;
        }
        maxSum = 0;
        for(int i = 1; i < len - 1; ++i ) {            
            maxSum = Math.max(0, A[i] + maxSum);
            maxEndingHere[i] = maxSum;
        }
        int maxDoubleSlice = 0;

        for(int i = 0; i < len - 2; ++i) {
            maxDoubleSlice = Math.max(maxDoubleSlice, maxEndingHere[i] + maxStartingHere[i+2]);
        }

        return maxDoubleSlice;

    }
}

You can find more information going to this Wikipedia link and in the Programming Pearls book.

Solution 4:[4]

Here is my solution https://github.com/dinkar1708/coding_interview/blob/master/codility/max_slice_problem_max_double_slice_sum.py

Codility 100% in Python

def solution(A):
"""
Idea is use two temporary array and store sum using Kadane’s algorithm
ending_here_sum[i] -  the maximum sum contiguous sub sequence ending at index i
starting_here_sum[i] - the maximum sum contiguous sub sequence starting with index i

Double slice sum should be the maximum sum of ending_here_sum[i-1]+starting_here_sum[i+1]

Reference -
https://rafal.io/posts/codility-max-double-slice-sum.html

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].
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.
"""
ar_len = len(A)
ending_here_sum = [0] * ar_len
starting_here_sum = [0] * ar_len

# the maximum sum contiguous sub sequence ending at index i
for index in range(1, ar_len - 2):  # A[X + 1] + A[X + 2] + ... + A[Y - 1]
    ending_here_sum[index] = max(ending_here_sum[index - 1] + A[index], 0)

# the maximum sum contiguous sub sequence starting with index i
for index in range(ar_len - 2, 1, -1):  # A[Y + 1] + A[Y + 2] + ... + A[Z - 1]
    starting_here_sum[index] = max(starting_here_sum[index + 1] + A[index], 0)

# Double slice sum should be the maximum sum of ending_here_sum[i-1]+starting_here_sum[i+1]
max_slice_sum = ending_here_sum[0] + starting_here_sum[2]
for index in range(1, ar_len - 1):
    max_slice_sum = max(max_slice_sum, ending_here_sum[index - 1] + starting_here_sum[index + 1])

return max_slice_sum

Solution 5:[5]

C# solution 100/100

public int solution(int[] A) {
        int[] forw = new int[A.Length];
        int[] rewi = new int[A.Length];

        bool isAllNeg = true;
        for (int i = 1; i < A.Length; i++)
        {
            forw[i] = Math.Max(0, forw[i - 1] + A[i]);
            if (A[i] > 0 && isAllNeg) isAllNeg = false;

        }

        if (isAllNeg)
            return 0;

        for (int i = A.Length - 2; i >= 0; i--)
        {
            rewi[i] = Math.Max(0, rewi[i + 1] + A[i]);
        }

        int maxsum = 0;
        for (int i = 1; i < A.Length - 1; i++)
        {
            maxsum = Math.Max(maxsum, forw[i - 1] + rewi[i + 1]);
        }

        return maxsum;
}

Solution 6:[6]

Without using extra memory, 100/100 C++:

#include <algorithm>

int solution(vector<int> &A) {
    int max_slice = 0;
    int max_slice_i = 0;

    int min_val = 0;

    int mss = 0;
    int mse = 0;

    int s = 1;

    int msmv = 0;

    int max_slice_i_orig = 0;
    int os = 1;

    for(size_t i = 1;i < A.size() - 1;i++)
    {
        int v = max_slice_i;

        if(max_slice_i > 0 && A[i] < 0)
        {
            if(A[i] < min_val)
            {
                v = max_slice_i_orig;
                s = os;
                min_val = std::max(A[i], -max_slice_i_orig); 
            } else
            {
                v = max_slice_i + A[i];               
            }                        
        } else
        {
            v = max_slice_i + A[i];
        }

        int new_orig_v = max_slice_i_orig + A[i];
        if(new_orig_v < 0)
        {
            max_slice_i_orig = 0;
            os = i + 1;
        } else
        {
            max_slice_i_orig = new_orig_v;
        }

        if(v > 0)
        {                    
            max_slice_i = v;                                   
        } else {            
            max_slice_i = 0;
            min_val = 0;
            s = i + 1;
        }

        if(max_slice_i > max_slice)        
        {
            mss = s;
            mse = i;
            msmv = min_val;
            max_slice = max_slice_i;
        }
    }

    // if all are positive
    if(msmv == 0)
    {
        if(mss == 1 && mse == A.size() - 2)
        {
            int min = 10001;
            for(int j = mss;j <= mse;j++)
            {
                if(A[j] < min)
                    min = A[j];
            }

            max_slice -= min;
        }
    }

    return max_slice;
}

Solution 7:[7]

Javascript implementation based on Abhishek Bansal's solution.100/100 on Codility.

function solution(A) {

  let maxsum=0;
  let max_end_at=Array(A.length);
  let max_start_at=Array(A.length);
  max_end_at[0]=max_start_at[A.length-1]=max_end_at[A.length-1]=max_start_at[0]=0;
  let {max}=Math;
  for(let i=1;i<A.length-1;i++){

  max_end_at[i]=max(0,max_end_at[i-1]+A[i]);
   }

  for(let n=A.length-2;n>0;n--){

  max_start_at[n]=max(0,max_start_at[n+1]+A[n]);
   }

  for(let m=1;m<A.length-1;m++){

    maxsum=max(maxsum,max_end_at[m-1]+max_start_at[m+1]);

    }
return maxsum;
}

Solution 8:[8]

The most clear Python solution among others:

def solution(A):
    mid = 1
    total = 0
    max_slice = 0

    for idx, end in enumerate(A[2:-1], start=2):

        if total < 0:
            mid = idx
            total = 0

        elif total == 0 and A[idx - 1] > A[mid]:
            mid = idx - 1
            total = end

        else:
            if A[mid] > end:
                total += A[mid]
                mid = idx
            else:
                total += end

        max_slice = max(max_slice, total)

    return max_slice

Solution 9:[9]

Using the idea from http://en.wikipedia.org/wiki/Maximum_subarray_problem and Abhishek Bansal's answer above. 100% test pass:

public class Solution {

public int solution(int[] A) {
    int[] maxEndingHere = maxEndingHere(A);
    int[] maxStartingHere = maxStartingHere(A);
    int maxSlice = 0;
    for (int i = 1; i < A.length-1;i++) {
      maxSlice = Math.max(maxSlice, maxEndingHere[i-1]+maxStartingHere[i+1]);
    }
    return maxSlice;
}


/**
 * Precalculate ending subarrays. Take into account that first and last element are always 0
 * @param input
 * @return
 */
public static int[] maxEndingHere(int[] input) {
    int[] result = new int[input.length];
    result[0] = result[input.length-1] = 0;
    for (int i = 1; i < input.length-1; i++) {
        result[i] = Math.max(0, result[i-1] + input[i]);
    }
    return result;
}

/**
 * Precalculate starting subarrays. Take into account that first and last element are always 0
 * @param input
 * @return
 */
public static int[] maxStartingHere(int[] input) {
    int[] result = new int[input.length];
    result[0] = result[input.length-1] = 0;
    for (int i = input.length-2; i >= 1; i--) {
        result[i] = Math.max(0, result[i+1] + input[i]);
    }
    return result;
}

}

Solution 10:[10]

Vb.net version of the above solution is as below:

Private Function solution(A As Integer()) As Integer
    ' write your code in VB.NET 4.0
    Dim Slice1() As Integer = Ending(A)
        Dim slice2() As Integer = Starting(A)
        Dim maxSUM As Integer = 0
        For i As Integer = 1 To A.Length - 2
            maxSUM = Math.Max(maxSUM, Slice1(i - 1) + slice2(i + 1))
        Next
        Return maxSUM
End Function
    Public Shared Function Ending(input() As Integer) As Integer()
        Dim result As Integer() = New Integer(input.Length - 1) {}
        result(0) = InlineAssignHelper(result(input.Length - 1), 0)
        For i As Integer = 1 To input.Length - 2
            result(i) = Math.Max(0, result(i - 1) + input(i))
        Next
        Return result
    End Function
    Public Shared Function Starting(input() As Integer) As Integer()
        Dim result As Integer() = New Integer(input.Length - 1) {}
        result(0) = InlineAssignHelper(result(input.Length - 1), 0)
        For i As Integer = input.Length - 2 To 1 Step -1
            result(i) = Math.Max(0, result(i + 1) + input(i))
        Next
        Return result
    End Function
        Private Shared Function InlineAssignHelper(Of T)(ByRef target As T, value As T) As T
            target = value
            Return value
        End Function

View result on codility

Solution 11:[11]

Here is an alternative solution to the proposed by me before, more readable and understandable:

int solution(vector<int> & A){
if(A.size() < 4 )
    return 0;
int maxSum = 0;
int sumLeft = 0;
unordered_map<int, int> leftSums;
leftSums[0] = 0;
for(int i = 2; i < A.size()-1; i++){
    sumLeft += A[i-1];
    if(sumLeft < 0)
        sumLeft = 0;
    leftSums[i-1] =  sumLeft;
}

int sumRight = 0;
unordered_map<int, int> rightSums;
rightSums[A.size()-1] =  sumRight;
for( int i = A.size() - 3; i >= 1; i--){
    sumRight += A[i+1];
    if(sumRight < 0)
        sumRight = 0;
    rightSums[i+1] = sumRight;
}

for(long i = 1; i < A.size() - 1; i++){
    if(leftSums[i-1] + rightSums[i+1] > maxSum)
        maxSum = leftSums[i-1] + rightSums[i+1];
}
return maxSum;

}

Solution 12:[12]

Well, I have my solution, may be not the best one bit 100%/100%, according to codility requierments.

#include<vector>
#include<unordered_map>
#include<algorithm>

using namespace std;

int solution(vector<int> &A) {
    unordered_map<size_t, int> maxSliceLeftToRight;
    maxSliceLeftToRight[1] = 0;
    unordered_map<size_t, int> maxSliceRightToLeft;
    maxSliceRightToLeft[A.size() - 2] = 0;
    int sum = 0;
    for (size_t i = 2; i < A.size() - 1; i++) {
        int tmpSum = max(sum + A[i - 1], 0);
        sum = max(A[i - 1], tmpSum);
        maxSliceLeftToRight[i] = sum;
    }
    sum = 0;
    for (size_t i = A.size() - 3; i > 0; i--) {
        int tmpSum = max(sum + A[i + 1], 0);
        sum = max(A[i + 1], tmpSum);
        maxSliceRightToLeft[i] = sum;
    }
    int maxDoubleSliceSum = 0;
    for (auto & entry : maxSliceLeftToRight) {
        int maxRight = maxSliceRightToLeft[entry.first];
        if (entry.second + maxRight > maxDoubleSliceSum)
            maxDoubleSliceSum = entry.second + maxRight;
    }
    return maxDoubleSliceSum;
}

Solution 13:[13]

Here 100% in python, might not be as elegant as some other solutions above, but considers all possible cases.

def solution(A):
#Trivial cases 
 if len(A)<=3:
  return 0 
 idx_min=A.index(min(A[1:len(A)-1]))
 minval=A[idx_min]
 maxval=max(A[1:len(A)-1])
 if maxval<0:
     return 0
 if minval==maxval:
     return minval*(len(A)-3)
#Regular max slice if all numbers > 0     
 if minval>=0:
  max_ending=0     
  max_slice=0
  for r in range(1,len(A)-1):
        if (r!=idx_min):     
         max_ending=max(0,A[r]+max_ending)
         max_slice = max(max_slice, max_ending)
  return max_slice  
#Else gets more complicated        
 else :
#First remove negative numbers at the beginning and at the end 
  idx_neg=1
  while A[idx_neg] <= 0 and idx_neg<len(A) :
   A[idx_neg]=0
   idx_neg+=1
  idx_neg=len(A)-2
  #<0 , 0
  while A[idx_neg] <= 0 and idx_neg > 0 :
   A[idx_neg]=0
   idx_neg-=1
#Compute partial positive sum from left
#and store it in Left array   
  Left=[0]*len(A) 
  max_left=0
  for r in range(1,len(A)-1):
      max_left=max(0,A[r]+max_left)
      Left[r]=max_left
#Compute partial positive sum from right
#and store it in Right array        
  max_right=0 
  Right=[0]*len(A)      
  for r in range(len(A)-2,0,-1):      
      max_right=max(0,A[r]+max_right)
      Right[r]=max_right   
#Compute max of Left[r]+Right[r+2].
#The hole in the middle corresponding
#to Y index of double slice (X, Y, Z)           
  max_slice=0
  for r in range(1,len(A)-3):
     max_slice=max(max_slice,Left[r]+Right[r+2])   
  return max_slice     
 pass

Solution 14:[14]

Think I got it based on Moxis Solution. Tried to point out the Intension.

    class Solution {
    public int solution(int[] A) { 

    int n = A.length - 1;

    // Array with cummulated Sums when the first Subarray ends at Index i
    int[] endingAt = new int[A.length];
    int helperSum = 0;

    // Optimal Subtotal before all possible Values of Y
    for(int i = 1; i < n; ++i ) {            
        helperSum = Math.max(0, A[i] + helperSum);
        endingAt[i] = helperSum;
    }

    // Array with cummulated Sums when the second Subarray starts at Index i
    int[] startingAt = new int[A.length];
    helperSum = 0;

    // Optimal Subtotal behind all possible Values of Y
    for(int i = (n - 1); i > 0; --i ) {   
        helperSum = Math.max(0, A[i] + helperSum);
        startingAt[i] = helperSum;
    }

    //Searching optimal Y
    int sum = 0;
    for(int i = 0; i < (n - 1); ++i) {
        sum = Math.max(sum, endingAt[i] + startingAt[i+2]);
    }

    return sum;

}

}

Solution 15:[15]

Here is the Python version of the proposed solution with complexity O(N) and %100 correctness and performance.

#Find the maximal sum of any double slice.
#https://app.codility.com/programmers/lessons/9- 
#maximum_slice_problem/max_double_slice_sum/

import sys

def solution(A):

 n=len(A)
 max_sum_endingat=[0]*n
 max_sum_startat=[0]*n

 if(n<=3):
     return 0
 else:

     for i in range(1,n-1):
         max_sum_endingat[i] =max(0,max_sum_endingat[i-1] + A[i])


     for i in range(n-2,0,-1):
         max_sum_startat[i] =max(0,max_sum_startat[i+1] + A[i])
     
     max_double=-sys.maxsize

     for k in range(1,n-1):
         max_double=max(max_double,max_sum_endingat[k-1]+max_sum_startat[k+1])

    
     return max_double

Solution 16:[16]

This is my solution. It got 92%. Its a modified version of the original concept except I'm keep track of a minimal value to use as the position Y, and I'm shifting the sum of the entire interval accordingly.

Note: If anyone has any idea why it's only 92% feel free to let me know

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int max = -10001, sum = 0, min=A[1];

        for(int i = 1; i < A.length-1; i++){
            sum += A[i];

            min = Math.min(A[i], min);
            max = Math.max(sum-min, max);

            if(sum - min < 0){
                sum = 0;
                min = A[i+1];
            }
        }

        return max;
    }
}

Solution 17:[17]

Java solution, 100/100

    class Solution {
        public int solution(int[] A) {
            // write your code in Java SE 8
            int maxEnd = 0, maxSlice = Integer.MIN_VALUE;
    
            for(int val : A) {
                maxEnd = Math.max(val, maxEnd + val);
                maxSlice = Math.max(maxSlice, maxEnd);
            }
    
            return maxSlice;
        }
    }

Related Questions