python - MaxDoubleSliceSum Algorithm -

i'm trying solve problem of finding maxdoubleslicesum value. simply, it's maximum sum of slice minus 1 element within slice (you have drop 1 element, , first , last element excluded also). so, technically first , last element of array cannot included in slice sum.

here's full description:

a non-empty zero-indexed array a consisting of n integers given. triplet (x, y, z), such 0 ≤ x < y < z < n, called double slice. sum of double slice (x, y, z) 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 following example double slices:

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

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

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

the goal find maximal sum of double slice.

write function:

def solution(a) that, given non-empty zero-indexed array a consisting of n integers, returns maximal sum of 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 sum of greater 17.

assume that:

n integer within range [3..100,000];

each element of array a integer within range [−10,000..10,000].

complexity:

expected worst-case time complexity o(n);

expected worst-case space complexity o(n), beyond input storage (not counting storage required input arguments).

elements of input arrays can modified.

here's try:

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

what makes me think may approach correct solution corners of problem may haven't been covered 9 out 14 test cases pass correctly (https://codility.com/demo/results/demoaw7wpn-pcv/) know can solved applying kadane’s algorithm forward , backward. i'd appreciate if can point out what's missing here.

this how i'd write algorithm.

assume start index of x=0, iteratively sum squares right.

• keep track of index of lowest int count, , subtract lowest int sum when use it. lets place y.
• keep track of max sum, , x, y, z values sum
• if sum ever turns negative save max sum result, long greater previous result.
• choose new x, should start looking after y , subtract 1 whatever index find. , repeat previous steps, until have reached end of list.

how might improvement?
potential problem case code: [7, 2, 4, -18, -14, 20, 22]
-18 , -14 separate array 2 segments. sum of first segment 7+2+4=13, sum of second segment 20. above algorithm handles case, yours might i'm bad @ python (sorry).

edit (error , solution): appears original answer brings nothing new thought problem, checked errors , found actual error occurs here: [-20, -10, 10, -70, 20, 30, -30] not handled correctly. exclude positive 10, returns 50 instead of 60.

it appears askers code doesn't correctly identify new starting position (my method shown in case 4), it's important restart iterations @ y instead of z because y deletes lowest number, possibly z fails test.