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.

Reference

Largest Sum Contiguous Subarray (Geeks for Geeks)
Maximum Slice tutorial PDF (Codility)

[cc lang="java" escaped="true"]
package 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;
	}
}
[/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.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);
	}	
}
[/cc]