# Codility ‘MaxSliceSum’ Solution

##### Short Problem Definition:

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

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.

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

• 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)

were

max_ending = max(0, max_ending+a)

This way max_ending would never be < 0, right?

• Tanuj Sharma
• Yun

I think the problem statement is misleading. It says “A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. Return the maximum sum of any slice of A."

So, with this test case [-3,-4,-5,100], the result should be 95(taking a pair of -5,100) and not 100.

• Kevin

Should be initialized with the most negative possible value, -1000000 not -100000 as above. All the values could be more negative than -100000