Question: http://codility.com/demo/take-sample-test/max_slice_sum

Question Name: MaxSliceSum

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

1 2 3 4 5 6 7 8 9 |
def solution(A): max_slice_ending_here = A[0] max_slice = A[0] for element in A[1:]: max_slice_ending_here = max(element, max_slice_ending_here+element) max_slice = max(max_slice, max_slice_ending_here) return max_slice |

Here is my solution, somewhat similar ðŸ™‚ Python 100/100

Classic question and classic solution ðŸ™‚

your solution is wrong

Why? It should be right.

PS: max_ending = max(0, max_ending + A[i]) is executed only when there is positive numbers.

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

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

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

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.

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.

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.

This solution fails for solution [-2,1]

Returned value: 1

Why is it incorrect?

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

10