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

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);
  }
}