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]

MaxDoubleSliceSum – Codility – Solution