# MaxSliceSum – Codility – Solution

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

The strategy is to keep track of the sum of current element + previous element and compare it to the current element to find the local max. The absolute max will be the highest local max.

Example

Integer A [] = { -2, -3, 4, -1, -2, 1, 5, -3 } has a max slice sum of 7.

A[i]nextSumlocalMax
-2NA-2
-3-5-3
414start of Max Slice
-133
-211
122
577MAX (end of Max Slice)
-344

Reference

```
123456789101112131415161718package com.codility.lesson09.maxslice;

public class MaxSliceSum {
public int solution(int[] A) {
int absoluteMax = A[0];
int localMax = A[0];
int nextSum = 0;
int currentElement = 0;

for (int i = 1; i < A.length; i++) {
currentElement = A[i];
nextSum = localMax + currentElement;
localMax = Math.max(A[i], nextSum);
absoluteMax = Math.max(absoluteMax, localMax);
}
return absoluteMax;
}
}

```

TestNG test cases for this problem which all passed:

```
12345678910111213141516171819202122232425262728293031323334package 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.MaxSliceSum;

public class MaxSliceSumTests {
private MaxSliceSum solution;

@BeforeTest
public void setUp() {
solution = new MaxSliceSum();
}

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

//https://en.wikipedia.org/wiki/Maximum_subarray_problem
new Object [] { new int [] {-2, 1, -3, 4, -1, 2, 1, -5, 4 }, 6 },
};
}

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

```