MaxDoubleSliceSum Algorithm

Question

I'm trying to solve the problem of finding the MaxDoubleSliceSum value. Simply, it's the maximum sum of any slice minus one element within this slice (you have to drop one element, and the first and the last element are excluded also). So, technically the first and the last element of the array cannot be included in any slice sum.

Here's the full description:

A non-empty zero-indexed array A consisting of N integers is given. A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice. 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].

For example, array A such that:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

contains the following example double slices:

double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,

double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,

double slice (3, 4, 5), sum is 0.

The goal is to find the maximal sum of any double slice.

Write a function:

def solution(A) that, given a non-empty zero-indexed array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

Assume that:

N is an integer within the range [3..100,000];

each element of array A is an integer within the range [−10,000..10,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Here's my try:

def solution(A):
    if len(A) <= 3:
        return 0
    max_slice = 0
    minimum = A[1]    # assume the first element is the minimum
    max_end = -A[1]   # and drop it from the slice
    for i in xrange(1, len(A)-1):
        if A[i] < minimum:        # a new minimum found
            max_end += minimum    # put back the false minimum
            minimum = A[i]        # assign the new minimum to minimum
            max_end -= minimum    # drop the new minimum out of the slice
        max_end = max(0, max_end + A[i])
        max_slice = max(max_slice, max_end)
    return max_slice

What makes me think that this may approach the correct solution but some corners of the problem may haven't been covered is that 9 out 14 test cases pass correctly (https://codility.com/demo/results/demoAW7WPN-PCV/) I know that this can be solved by applying Kadane’s algorithm forward and backward. but I'd really appreciate it if someone can point out what's missing here.

It tells you what the tests are; why don't you try replicating the tests and looking at the output for a minimal failing example? You can test against a brute-force algorithm to get the reliable answer. — Veedrac
This question addresses the same problem in the same context (different language but the idea is there): stackoverflow.com/questions/20660989/max-double-slice-sum — koukouviou
Found the error, try [-20, -10, 10, -70, 20, 30, -30]. It should be 60 not 50 — Alter

Alter Alter · Accepted Answer · 2015-04-15T04:12:38

This is just how I'd write the algorithm.

Assume a start index of X=0, then iteratively sum the squares to the right.

Keep track of the index of the lowest int as you count, and subtract the lowest int from the sum when you use it. This effectively lets you place your Y.
Keep track of the max sum, and the X, Y, Z values for that sum
if the sum ever turns negative then save the max sum as your result, so long as it is greater than the previous result.
Choose a new X, You should start looking after Y and subtract one from whatever index you find. And repeat the previous steps, do this until you have reached the end of the list.

How might this be an improvement?
Potential problem case for your code: [7, 2, 4, -18, -14, 20, 22]
-18 and -14 separate the array into two segments. The sum of the first segment is 7+2+4=13, the sum of the second segment is just 20. The above algorithm handles this case, yours might but I'm bad at python (sorry).

EDIT (error and solution): It appears my original answer brings nothing new to what I thought was the problem, but I checked the errors and found the actual error occurs here: [-20, -10, 10, -70, 20, 30, -30] will not be handled correctly. It will exclude the positive 10, so it returns 50 instead of 60.

It appears the askers code doesn't correctly identify the new starting position (my method for this is shown in case 4), it's important that you restart the iterations at Y instead of Z because Y effectively deletes the lowest number, which is possibly the Z that fails the test.

MaxDoubleSliceSum Algorithm

1 Answers