最大双切片求和算法

Question

我在尝试解决求MaxDoubleSliceSum值的问题。简单地说，它是任何切片的最大和减去该切片中的一个元素(您必须删除一个元素，并且第一个和最后一个元素也被排除在外)。因此，从技术上讲，数组的第一个和最后一个元素不能包含在任何片和中。

以下是完整描述：

给出了一个非空的零索引数组A由N整数组成。三元组（X， Y， Z），使得0≤X

例如，数组< code>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，3，7），总和2 6 4 5− 1=16，

双切片（3，4，5），总和0。

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

写一个函数：

< code>def solution(A)在给定由< code>N个整数组成的非空零索引数组< code>A的情况下，返回任何double slice的最大和。

例如，给定：

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。

假设:

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

数组< code>A的每个元素都是< code >(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

让我认为这可能接近正确的解决方案，但问题的一些角落可能还没有被覆盖，那就是14个测试用例中有9个正确通过（https://codility.com/demo/results/demoAW7WPN-PCV/），我知道这可以通过向前和向后应用Kadane的算法来解决。但如果有人能指出这里缺少什么，我将不胜感激。

Answer 1

这就是我写算法的方式。

假设起始索引为X=0，然后迭代求和右边的平方。

• 计数时跟踪最低整数的索引，并在使用时从总和中减去最低整数。这样可以有效地放置Y。
• 跟踪最大总和以及该总和的X、Y、Z值
• 如果总和变为负数，则保存最大总和作为结果，只要它大于之前的结果
• 选择一个新的X，你应该开始照顾Y，并从你找到的索引中减去一。重复前面的步骤，直到列表结束

这会是怎样的改进
代码的潜在问题案例：[7、2、4、-18、-14、20、22]
-18和-14将数组分为两段。第一段的总和是7 2 4=13，第二段的总和只有20。上面的算法可以处理这种情况，您的算法可能会，但我不擅长python（对不起）。

编辑（错误和解决方案）：看来我的原始答案对我认为是问题没有任何新的东西，但我检查了错误，发现实际错误发生在这里：[-20，-10，10，-70，20，30，-30]将无法正确处理。它将排除正 10，因此返回 50 而不是 60。

看起来提问者代码没有正确识别新的起始位置（我的方法在案例4中所示），重要的是在Y而不是Z处重新启动迭代，因为Y有效地删除了最低的数字，这可能是测试失败的Z。

Answer 2

这个要用Kadane的算法从两个方向解决。

裁判：

Python协作解决方案

C 解决方案 - 优酷教程

JAVA解决方案

def compute_sum(start, end, step, A):
    res_arr = [0]
    res = 0
    for i in range(start, end, step):
        res = res + A[i]
        if res < 0:
            res_arr.append(0)
            res = 0
            continue
        res_arr.append(res)
    return res_arr    

def solution(A):

    if len(A) < 3:
        return 0

    arr = []
    left_arr = compute_sum(1, len(A)-1, 1, A)
    right_arr = compute_sum(len(A)-2, 0, -1, A)

    k = 0
    for i in range(len(left_arr)-2, -1, -1):
        arr.append(left_arr[i] + right_arr[k])
        k = k + 1
 
    return max(arr)