# 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

```
12345678910111213141516171819202122package 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;
}
}

```

TestNG test cases for this problem which all passed:

```
12345678910111213141516171819202122232425262728293031package 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);
}
}

```