python - 如何从两侧找到最大数组

Question

给定一个整数数组 A，我需要从数组 A 的左端或右端选择 B 元素以获得最大和.如果 B = 4，那么您可以选择前四个元素或后四个元素，或者一个在前面，三个在后面等等。

示例输入:

A = [5, -2, 3, 1, 2]
B = 3

正确答案是 8(从左边选择 5，从左边选择 1 和 2对)。

我的代码:

def solve(A, B):
    n = len(A)
    # track left most index and right most index i,j
    i = 0
    j = n-1
    Sum = 0
    B2 = B  # B for looping and B2 for reference it
    # Add element from front
    for k in range(B):
        Sum += A[k]
        
    ans = Sum
    # Add element from last
    for _ in range(B2):
       # Remove element from front
       Sum -= A[i]
       # Add element from last
       Sum += A[j]
       ans = max(ans, Sum)

    return ans

但我得到的答案是 6。

Answer 1

解决方案

def max_bookend_sum(x, n):
    bookends = x[-n:] + x[:n]
    return max(sum(bookends[i : i + n]) for i in range(n + 1))

解释

令n = 3并取x,

>>> x = [4, 9, -7, 4, 0, 4, -9, -8, -6, 9]

获取“右”n 元素，与“左”n 连接:

>>> bookends = x[-n:] + x[:n]
>>> bookends  # last three elements from x, then first three
[-8, -6, 9, 4, 9, -7]

获取 n 元素的“滑动窗口”组:

>>> [bookends[i : i + n] for i in range(n + 1)]
[[-8, -6, 9], [-6, 9, 4], [9, 4, 9], [4, 9, -7]]

现在，不是生成子列表，而是对它们求和，取最大值:

>>>  max(sum(bookends[i : i + n]) for i in range(n + 1))
22

对于评论中的大型数组 A:

>>> max(sum(bookends[i : i + n]) for i in range(n + 1))
6253