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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;

  }

}

TestNG test cases for this problem which all passed:

1
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
32
33
34
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);

  } 

}