Codility ‘MaxSliceSum’ Solution

Short Problem Definition:

Find a maximum sum of a compact subsequence of array elements.




expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)


The only difference to the example given by Codility is the minimal slice length, which is 1.

def solution(A):
    max_ending = max_slice = -1000000
    for a in A:
        max_ending = max(a, max_ending +a)
        max_slice = max(max_slice, max_ending)
    return max_slice

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

  • BruceFromSeattle

    The solution is too clever and elegant to be the “painless/easy” solution. And it’s space complexity O(1). How about this (in C#) which is space O(N):
    public int solution(int[] A)
    int n = A.Length;
    long[] ps = new long[n];
    long[] minps = new long[n];
    long maxSliceSum = long.MinValue;
    // first calculate prefix sums
    ps[0] = A[0];
    for (int i = 1; i < n; i++)
    ps[i] = A[i] + ps[i – 1];
    // then calculate min prefix sums up to but not including current index
    minps[0] = 0;
    for (int i = 1; i < n; i++)
    if (ps[i – 1] < minps[i – 1])
    minps[i] = ps[i – 1];
    minps[i] = minps[i – 1];
    // then calculate the max diff of corresponding elements in these 2 arrays
    for (int i = 0; i maxSliceSum)
    maxSliceSum = ps[i] – minps[i];
    // probably could combine loops
    return (int) maxSliceSum;

  • Can you please elaborate on why slice size 1 brings you to “max(a, max_ending +a)”? In the PDF the line is “max(0, max_ending +a)”. I kinda understand that that is due to the PDF expecting slices to have at least 2 elements, but this is not really clear to me. Thank you.

  • sirhuxley

    Seems like it would be better if:

    max_ending = max(a, max_ending +a)


    max_ending = max(0, max_ending+a)

    This way max_ending would never be < 0, right?