Solution to Max-Double-Slice-Sum by codility

25 Jan

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

47 Replies to “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:
        |——————–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.

  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:
    http://rafal.io/posts/codility-max-double-slice-sum.html
    https://codility.com/demo/results/demoVUMMR9-JH3/

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

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

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

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

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

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

Leave a Reply

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

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!