Max double slice sum

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

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

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

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

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;

}

}

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

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

Single-loop, no extra memory dynamic programming solution in Python:

def solution(A):
    max_gap_sum = 0
    gapless_sum, gap_sum = 0, float("-inf")
    for v in A[1:-1]:
        gapless_sum, gap_sum = max(gapless_sum + v, 0), max(gap_sum + v, gapless_sum)
        max_gap_sum = max(max_gap_sum, gap_sum)
    return max_gap_sum

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