# Solution to Max-Slice-Sum by codility

26 Jan

Question Name: MaxSliceSum

The classic maximum subarray problem. It should be the very first question in this lesson.

### 21 Replies to “Solution to Max-Slice-Sum by codility”

1. Karol says:

Here is my solution, somewhat similar 🙂 Python 100/100

• Sheng says:

Classic question and classic solution 🙂

• zaid says:

• Sheng says:

Why? It should be right.
PS: max_ending = max(0, max_ending + A[i]) is executed only when there is positive numbers.

• Tony Sun says:

You should double check whether you know what you are talking about next time before you criticise someone else’s solution!

• Tony Sun says:

This is less optimal though still O(n) it has to find out the max of A first; max itself is O(n).

2. Greg says:

How this problem differs from max slice problem described in the lesson (https://codility.com/media/train/7-MaxSlice.pdf)?
O(n) algorithm presented at the end is very similar to your solution and it works fine as long as slice sums are positive. Lesson does not mention negative numbers handling though

• Sheng says:

In the lesson, the slice could be empty, whose sum is zero. Therefore the maximum slice sum would zeor or more.
In the execise, the slice could NOT be empty. And the maximum slice sum might be negative.

• Tony Sun says:

I don’t think the key difference is whether the array can be empty. I think algorithm in the lessson is fundamentally wrong. Because it initialises both max_ending and max_slice to be 0, hence the algorithm in the lesson won’t work for a single negative array e.g. A = [-10]. What’s funy is in the lesson it did mention the array elements can be negative.
I am really surprised that as of today (Nov 2016) Codility hasn’t really fixed this, probably because nobody bothers reporting it.

• Sheng says:

I believe the lesson is correct. When A = [-10], the result is 0, as the maximum slice is an empty slice [].
As I said, in the lesson, empty slice is permitted, while it’s not in the practice.

• Peter says:

I red in several places that unlike in the lesson, the slice could not be empty in the exercise. I don’t understand where does that come from. “A non-empty array A consisting of N integers is given”, which is the input, not the slice, so so far the slice can be empty. “A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A" so it should be acceptable that P == Q and so far the slice can still be empty. "The sum of a slice (P, Q) is the total of A[P] + A[P+1] + … + A[Q]" is no way to tell that the slice cannot be empty because it reads from P increments till you reach Q included, so P == Q is acceptable despite the "A[P+1]" and the slice can still be empty. If they have wanted the slice not to be empty, they should have written P < Q instead of P ≤ Q.

• Sheng says:

When P == Q, the slice is a single-element slice as input[P] (or equally input[Q]).

As you said, in computing the slice sum, both ends are included.

• Noob says:

Hi Sheng,

Can you please explain why (2, 2) is a slice of A that has sum −6 has in the exercise it looks they are taking slicing index 2 with 2. Also I thought the statement 0 ≤ P ≤ Q < N means any slice element must be zero or greater (not negative) and must be less than n, this means they number element cannot be more than the Array length ?

• Sheng says:

Hi Noob,

The slice (2, 2) of the input array [3, 2, -6, 4, 0] is [-6], whose sum is -6.

Also, the P and Q in the restriction `0 ≤ P ≤ Q < N` is the index (NOT the value), which is always and naturally zero or positive.

3. rishi says:

This solution fails for solution [-2,1]

• Sheng says:

Returned value: 1
Why is it incorrect?

4. Srinivas says:

What would be the result for this input ? [3, 3, -2, 2, 4, 0]

• Sheng says:

10

5. Rajasekar Palanisamy says:

C# solution

6. lorem ipsum says:

scala

7. Ghaith says:

C O(N) Solution
https://app.codility.com/demo/results/trainingVTW26A-737/