# Solution to Max-Double-Slice-Sum by codility

25 Jan

Question Name: MaxDoubleSliceSum

A variant of the classic maximum subarray problem. We should travel the array twice. For the first travel, we compute and record the maximum sub-array sum, which ends at each position. At the second reverse travel, we compute and record the maximum sub-array sum, which starts at each position. Finally, we combine two sub-arrays into one double slice, and find out the maximum sum.

Update on 2016/12/12: as VuThanhCong pointed out in the comment, the range to compute max_ending_here and max_beginning_here could be smaller by one element: max_ending_here should be calculated from value in range(1, N-2); max_beginning_here should be calculated from value in range(N-2, 1, -1).

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

1. Pedro says:

Nice solution and very simple to understand!!!
Mine only uses one for loop and O(1) space complexity, BUT, it is not readable at all, and it took me a long time to find it. Im gonna try yours in C# now.
Nice blog by the way, I always come here after I finish the problems to compare solutions

• Sheng says:

Thanks for visiting! By the way, if you find a better solution for some questions, please share with us!

• Pedro says:

I really don´t think it´s better, cause the algorithm behind is hard for me to explain. Also, I don´t know Python, I´m working with C# now. In any case, if I wanted to post some code, could you tell me how to insert code in the comments in a “pretty way”?? I mean with the different colors and stuff

• Sheng says:

You could use the tags like:
<pre class=”lang:python decode:true” title=”Solution to XXX”>def solution(A):
return 0</pre>
For c#, in the tag, the lang:c# would work. Also, with your permit, I am very happy to append your solution to my post, with your author information.

• Pedro says:

Forget it, it is mixing the for with an if statement, dont know why…

• Sheng says:

Could you please send me an email (yusheng123 at gmail dot com) regarding your solution? And is it alright to post your solution in this blog? Thanks!

2. Pedro says:

Also, I would like to see your solution to fluorum2014, I did it but I think my solution was kind of cumbersome and hard to explain, although it works 100/100. I´d like to see a simpler approach cause I know I could not have found mine within the 2 hour limit.

• Sheng says:

Sorry, I cannot solve it…

3. Rahul Sinha says:

Sheng , I am not much good at calculating complexity , Can you explain me here Why this program’s complexity is O(N) instead of O(N^3) , as we are traversing through loop 3 times..

• Sheng says:

Each for loop to traverse through the array would be O(N). And they are executed one by one. So totally the complexity is O(N) + O(N) + O(N) = O(N).
If the code is like:

The complexity is O(N^3).

4. Dmitrym says:

Hi, found another way without need to reserve space:

UPDATE by Dmitrym via Email:

• Sheng says:

Sorry, it did not show completely. Please include the original code inside the <pre></pre> block. Please do not replace the < and so on.

• Sheng says:

• Yuval says:

Hi,
Can you explain your code? I ran it on several small test cases and it gave the wrong answer.

• Sheng says:

I can only understand part of it. Consider the Max-Double-Slice at the previous position, it must be one of the follwoing three cases:
|——————–X|
|———X———–|
|X——————–|
where X is the missing item A[Y].
Come to the current position, we could get:
|——————–X| Y
|———X———–| Y
|X——————–| Y
The variable maxdCand2 is filling X to get a candidate for the Max-Double-Slice endng with current position. While the variable maxDouble is filing Y. Finally, maxCurrent is a candidate, in which Y is missing.
But I do not know how to prove its correctness. Emailed the original author, and hope we can get some update.

• Sheng says:

Hi, if you got some test cases with wrong output, could you please share some of them?

5. Dmitrym says:

Also I’d rewrite original solution for cleaner looking:

• Sheng says:

The price is losing some readability, with the new and meaningless variable name. Personally, I prefer the original one.

6. Lumiere says:

Why is the second subarray starts at position i+2? isn’t it suppose to be i + 1?

• Sheng says:

In the definition of double slice, there is ONE gap cell between the two segments.

7. Moataz says:

Hello, I thought that the line
max_ending_here_temp = max(0, A[index]+max_ending_here_temp)
should be replaced by
max_ending_here_temp = max(A[index], A[index]+max_ending_here_temp)
because the maximum sum until index could be either ‘A[index]’ which accounts for the item alone or the other term.
If the arrays contains all negative numbers, the answer should be some negative number but your code (and amazingly codility themselves) want it to be zero. For example, for the sequence [0, 10, -5, -2, 0], your code returns 10 instead of 8 for slice (0,2,4) (and that what also codility wants!). Did I understand something wrong? Thanks

• Sheng says:

Hello, my solution should be right. As the challenge definition, the slice might be empty! Therefore, if the arrays contains all negative numbers, the answer is zero, not any negative number.

• Pedro Borges says:

Wow, that’s a tricky one, a simple statement that the slice can be empty implies no negative slices… that was tricky, was banging my head on that… back to the problem, thanks.

• Pedro Borges says:

Shouldn’t the last for-loop in your solution be xrange(1, A_len-3) ? no need to parse cases max_ending_here[0] & max_beginning_here[A_len-1] since they were not populated.

• Sheng says:

Not necessary. Please take a look at the first two for loops. I did not travel all elements when computing max_ending_here and max_beginning_here array.

• fcagalj says:

Where in challenge is defined that slice might be empty? And wouldn’t it empty slice be in collision with condition 0 ≤ X < Y < Z < N (A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice)?
Respecting this condition I don't think that you have correct solutions. And I don't think it is possible to solve this beyond N2 time complexity.

• Sheng says:

The challenge statement: The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + … + A[Y − 1] + A[Y + 1] + A[Y + 2] + … + A[Z − 1].
If X = Y – 1, the left slice is empty; if Y = Z – 1, the right slice is empty.

• fcagalj says:

I understood that, tnx. But fact that double slice with X = Y – 1 is empty doesn’t follow from the statement “The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + … + A[Y − 1] + A[Y + 1] + A[Y + 2] + … + A[Z − 1]”.
You can conclude that from example “double slice (3, 4, 5), sum is 0”, but it is not precise defined in assignment. It would be much harder to solve task if it is named otherwise than “double slice”.

• Sheng says:

Double slice with X = Y – 1 may be not empty. But double slice with X = Y – 1 AND Y = Z – 1 is empty.

8. Ishaq says:

I did it like this (and I hate it), looking at your solution now:

• Sheng says:

Enjoy coding 🙂

9. Adding a Java Solution also based on the wikipedia link, the programming pearls books and this link:
http://rafal.io/posts/codility-max-double-slice-sum.html
https://codility.com/demo/results/demoVUMMR9-JH3/

10. TD says:

What happens if all the elements in the array are negatives ? The precondition doesn’t say that the array cannot have all negatives. I am a bit confused. Can anybody explain ? Thanks

11. VuThanhCong says:

Thank you for a nice solution!
I think max_ending_here should be calculated from value in range(1, N-2)
and max_beginning_here should be calculated from value in range(N-2, 1, -1).

• Sheng says:

You are absolutely right. Thanks!

12. Valmín says:

Hi there.
My C++ solution is similar to yours but with two minor differences: I only store the right slices sums (between Y and Z) because I calculate the left slices sums on the fly and I use a forward list (singly-linked list) to store those right slices sums because they are calculated in reverse but are read later from front to back. For some reason I thought that would make more sense than using a vector array but it’s basically the same thing.
O(N) space and O(N) time complexities are both met.

13. Zhou says:

Inspired by Dmitrym’s solution. O(N) time O(1) space.

• Sheng says:

Thanks for sharing the code with comments 🙂

14. Hi ,
I came up with the following Python code.
Does is violate the O(N) space complexity restriction ?

• Sheng says:

[Sorry, I am not familiar with numpy.] Not 100% sure, but it seems to violate both O(N) space and O(N) time restriction.

15. Hi Sheng,
I have this solution that give me some troubles.
I can not understand, it is 100% correct but the performances stop at 85% (the complexity remains O (N)). There is an error in the last performance test, but I can not find the error case to figure out where it is wrong. Can someone illuminate me?

The algorithm is simple and solves the problem as a Maximum subarray problem, identifying the minimum value to subtract within the considered interval (equal to zero if it is positioned at one of the two extremes).

• Sheng says:

Sorry, I do not have time to debug the solution. In this case, I would suggest to:
1. Implement the brute force solution;
2. Generate a list with random numbers;
3. Go through both solutions with the random list
3.a if the results are the same, continue from step #2;
3.b if the results are different, you found the testing case 🙂

To make the process more efficient, I would:
1. Make the numbers list short;
2. Make the numbers’s range small and around 0 (to include negative, zero, and positive numbers).

16. marble says:

17. Robert says:

Hello Sheng,

solution([1, 2, 3, 4])
3

Does ‘3’ look correct to you? I think the answer should be ‘2’.

===========================================================

Hello Sheng,

One of the tests at Colidity after submitting for MaxDoubleSliceSum is with the following data:

A = [5, 17, 0, 3]

Your solution picks the highest of A[1] and A[2], it works for this test, but is that correct behavior?

With the data [1, 2, 3, 4] your solution picks 3. The reason [5, 17, 0, 3] works is because A[2] happens to be lower.

PS:

I posted once before, but for some strange reason my post was deleted.

Regards
Robert

• Sheng says:

Hi Robert, solution([1, 2, 3, 4]) == 3 looks correct to me, with the double slice (0, 1, 3). For A = [5, 17, 0, 3], the result slice is (0, 2, 3).