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)

\n

这应该使用 Kadane\xe2\x80\x99s 算法从两个方向解决。

\n

参考：

\n

Python Codility 解决方案

\n

C++ 解决方案 - YouTube 教程

\n

JAVA解决方案

\n

def compute_sum(start, end, step, A):\n    res_arr = [0]\n    res = 0\n    for i in range(start, end, step):\n        res = res + A[i]\n        if res < 0:\n            res_arr.append(0)\n            res = 0\n            continue\n        res_arr.append(res)\n    return res_arr    \n\ndef solution(A):\n\n    if len(A) < 3:\n        return 0\n\n    arr = []\n    left_arr = compute_sum(1, len(A)-1, 1, A)\n    right_arr = compute_sum(len(A)-2, 0, -1, A)\n\n    k = 0\n    for i in range(len(left_arr)-2, -1, -1):\n        arr.append(left_arr[i] + right_arr[k])\n        k = k + 1\n \n    return max(arr)\n

\n