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)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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);
}
}