MaxDoubleSliceSum – Codility – Solution

Java solution to Codility MaxDoubleSliceSum problem (Lesson 9 – Maximum Slice) which scored 100%. The problem is to find the maximum sum of two sub-arrays of an integer array.

The strategy is to:

  • compute local max (not less than 0) up to each element in array going a) forward and b) backward
  • find absolute max double slice by going through a) and b) to compute each double slice sum

Example

Integer array A = { 3, 2, 6, -1, 4, 5, -1, 2 }
Running sum slice1LocalMax (going forward) = { 0, 2, 8, 7, 11, 16, 15, 0 }
Running sum slice2LocalMax (going backward) = { 0, 16, 14, 8, 9, 5, 0, 0 }

References

MaxDoubleSliceSum Codility Algorithm (Stack Overflow)
Codility Max Double Slice Sum (Rafal’s Blog)

[cc lang="java" escaped="true"]
package com.codility.lesson09.maxslice;

public class MaxDoubleSlice {
	public int solution(int[] A) {
		int[] slice1LocalMax = new int[A.length];
		int[] slice2LocalMax = new int[A.length];
		
		//start from i=1 because slice can't start at index 0
		for(int i = 1; i < A.length-1; i++) { slice1LocalMax[i] = Math.max(slice1LocalMax[i-1] + A[i], 0); } //start from i=A.length-2 because slice can't end at index A.length-1 for(int i = A.length-2; i > 0; i--){
			slice2LocalMax[i] = Math.max(slice2LocalMax[i+1]+A[i], 0);
		}
		
		int maxDoubleSliceSum = 0;
		
		//compute sums of all slices to find absolute max
		for(int i = 1; i < A.length-1; i++) {
			maxDoubleSliceSum = Math.max(maxDoubleSliceSum, slice1LocalMax[i-1] + slice2LocalMax[i+1]);
		}
		
		return maxDoubleSliceSum;
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson09.maxslice;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson09.maxslice.MaxDoubleSlice;

public class MaxDoubleSliceSumTests {
	private MaxDoubleSlice solution;
	
	@BeforeTest
	public void setUp() {
		solution = new MaxDoubleSlice();
	}

	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] { new int [] { 3, 2, 6, -1, 4, 5, -1, 2 }, 17 },
			new Object [] { new int [] { -2 -3, 4, -1, -2, 1, 5, -3 }, 9 },
			new Object [] { new int [] { 1, 2, 3 }, 0 },
		};
	}

	@Test(dataProvider = "test1")
	public void verifySolution(int [] pA, int pExpected) {		
		Assert.assertEquals(solution.solution(pA), pExpected);
	}	
}
[/cc]