python - MaxDoubleSliceSum 算法

Question

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

这里是完整的描述:

一个非空的零索引数组 A由 N 组成给出整数。 三胞胎(X, Y, Z) , 这样 0 ≤ X < Y < Z < N , 称为双切片。 双切片之和(X, Y, 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, 3, 7) , 和是 2 + 6 + 4 + 5 − 1 = 16 ,

双片 (3, 4, 5) , 和是 0 .

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

写一个函数:

def solution(A) 即，给定一个非空的零索引数组 A由 N 组成整数，返回任何双切片的最大总和。

例如，给定:

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

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

Answer 1

Python 解决方案 O(N)

这应该使用 Kadane 的算法从两个方向解决。

引用:

Python Codility Solution

C++ solution - YouTube tutorial

JAVA solution

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)