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

37 thoughts on “Solution to Max-Double-Slice-Sum by codility

  1. 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

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

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

  3. 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).

  4. 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.

      • 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:
        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.

  5. Also I’d rewrite original solution for cleaner looking:

  6. 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”.

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

  8. Adding a Java Solution also based on the wikipedia link, the programming pearls books and this link:

  9. 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

  10. 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).

Leave a Reply

Your email address will not be published. Required fields are marked *