Codility ‘MaxSliceSum’ Solution

Short Problem Definition:

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

Link

MaxSliceSum

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

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

Solution:
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.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • 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];
    else
    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;
    }