python – MaxDoubleSliceSum算法

我正在尝试解决找到MaxDoubleSliceSum值的问题.简单来说,它是任何切片减去该切片中一个元素的最大总和(您必须删除一个元素,并且还要排除第一个和最后一个元素).因此,从技术上讲,数组的第一个和最后一个元素不能包含在任何切片总和中.

这是完整的描述：

给出了由N个整数组成的非空零索引数组A.
三重态(X,Y,Z),使得0≤X<1. Y< Z< N,称为双切片.
双切片之和(X,Z)是A [X 1] A [X 2]的总和… A [Y – 1] A [Y 1] A [Y 2] … A [ Z – 1].

例如,数组A使得：

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

包含以下示例双切片：

双切片(0,3,6),总和是2 6 4 5 = 17,

双切片(0,7),总和是2 6 4 5 – 1 = 16,

双切片(3,4,5),总和为0.

目标是找到任何双切片的最大总和.

写一个函数：

解决方案(一)
在给定由N个整数组成的非空零索引数组A的情况下,返回任何双切片的最大总和.

例如,给定：

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

函数应该返回17,因为数组A的双片没有大于17的和.

假使,假设：

N是[3..100,000]范围内的整数;

数组A的每个元素都是[-10,000..10,000]范围内的整数.

复杂：

预期的最坏情况时间复杂度是O(N);

预期的最坏情况空间复杂度是O(N),超出输入存储(不计入输入参数所需的存储).

可以修改输入数组的元素.

这是我的尝试：

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

是什么让我觉得这可能接近正确的解决方案,但问题的某些角落可能没有被覆盖是9个14个测试用例正确通过(https://codility.com/demo/results/demoAW7WPN-PCV/)
我知道这可以通过向前和向后应用Kadane的算法来解决.但如果有人能指出这里遗漏的东西,我真的很感激.