Codility Max Double Slice Sum

Solution to Codility Max Double Slice Sum problem.

We can use Kadane’s algorithm from two directions. First, we can safely ignore A[0] and A[N-1] since by definition they can’t be a part of any double-slice sum.

Now, define K1[i] as the maximum sum contiguous subsequence ending at index \(i\), and similarly, define K2[i] as the maximum sum contiguous subsequence starting with index \(i\).

Then, iterate over \(i\), and find the maximum sum of K1[i-1]+K2[i+1]. This is the max double slice sum.

The 100/100 Java code:

public int solution(int[] A) {
  int N = A.length;
  int[] K1 = new int[N];
  int[] K2 = new int[N];

  for(int i = 1; i < N-1; i++){
    K1[i] = Math.max(K1[i-1] + A[i], 0);
  }
  for(int i = N-2; i > 0; i--){
    K2[i] = Math.max(K2[i+1]+A[i], 0);
  }

  int max = 0;

  for(int i = 1; i < N-1; i++){
    max = Math.max(max, K1[i-1]+K2[i+1]);
  }

  return max;
}