Question: http://codility.com/demo/take-sample-test/max_double_slice_sum
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).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | def solution(A): A_len = len(A) # The length of array A # Get the sum of maximum subarray, which ends this position # Method: http://en.wikipedia.org/wiki/Maximum_subarray_problem max_ending_here = [0] * A_len max_ending_here_temp = 0 for index in xrange(1, A_len-2): max_ending_here_temp = max(0, A[index]+max_ending_here_temp) max_ending_here[index] = max_ending_here_temp # Get the sum of maximum subarray, which begins this position # The same method. But we travel from the tail to the head max_beginning_here = [0] * A_len max_beginning_here_temp = 0 for index in xrange(A_len-2, 1, -1): max_beginning_here_temp = max(0, A[index]+max_beginning_here_temp) max_beginning_here[index] = max_beginning_here_temp # Connect two subarray for a double_slice. If the first subarray # ends at position i, the second subarray starts at position i+2. # Then we compare each double slice to get the one with the # greatest sum. max_double_slice = 0 for index in xrange(0, A_len-2): max_double_slice = max(max_double_slice, max_ending_here[index] + max_beginning_here[index+2] ) return max_double_slice |
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
Thanks for visiting! By the way, if you find a better solution for some questions, please share with us!
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
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.
Forget it, it is mixing the for with an if statement, dont know why…
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!
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.
Sorry, I cannot solve it…
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..
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).
Hi, found another way without need to reserve space:
UPDATE by Dmitrym via Email:
Sorry, it did not show completely. Please include the original code inside the <pre></pre> block. Please do not replace the < and so on.
Thanks for sharing your solution!
Hi,
Can you explain your code? I ran it on several small test cases and it gave the wrong answer.
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.
Hi, if you got some test cases with wrong output, could you please share some of them?
Nice thought!
Also I’d rewrite original solution for cleaner looking:
The price is losing some readability, with the new and meaningless variable name. Personally, I prefer the original one.
Why is the second subarray starts at position i+2? isn’t it suppose to be i + 1?
In the definition of double slice, there is ONE gap cell between the two segments.
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
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.
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.
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.
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.
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.
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.
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”.
Double slice with X = Y – 1 may be not empty. But double slice with X = Y – 1 AND Y = Z – 1 is empty.
I did it like this (and I hate it), looking at your solution now:
Enjoy coding 🙂
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/
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
It is totally fine if the elements are negative. Please read the Wikipedia at: https://en.wikipedia.org/wiki/Maximum_subarray_problem for all the details.
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).
You are absolutely right. Thanks!
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.
Inspired by Dmitrym’s solution. O(N) time O(1) space.
Thanks for sharing the code with comments 🙂
Hi ,
I came up with the following Python code.
Does is violate the O(N) space complexity restriction ?
[Sorry, I am not familiar with numpy.] Not 100% sure, but it seems to violate both O(N) space and O(N) time restriction.
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).
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).
Hello Sheng,
Regarding your solution:
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
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).