Can't implement Maximal subarray with length constraint algorithm-CodePudding

I can't get this algorithm working. What is the array of partial sums B[]? Does it have 1 element less than A[]? For A = [8, -1, -1, 4, -2, -3, 5, 6, -3] it will look like B = [7, 6, 10, 8, 5, 10, 16, 13]

Tried the following Python code:

def maxSubseq(a, k):
    maxSum = -999999999999

    b = [a[0]   a[1]]
    for x in range(1, len(a) - 1):
      b.append(b[x - 1]   a[x   1])

    from collections import deque
    deq = deque()
    for q in range(len(b)):
        if deq and q - deq[0] > k:
            deq.popleft()
        while deq and b[deq[-1]] > b[q]:
            deq.pop()
        deq.append(q)

        if b[q] - b[deq[0]] > maxSum:
            maxSum = b[q] - b[deq[0]]
    return maxSum

print(maxSubseq([8, -1, -1, 4, -2, -3, 5, 6, -3], 8))

11 - but should be 16

CodePudding user response：

B should be [0,8, 7, 6, 10, 8, 5, 10, 16, 13]

def maxSubseq(a, k):
    maxSum = -999999999999

    b = [0, a[0]]
    for x in range(1, len(a)):
      b.append(b[x]   a[x])
    from collections import deque
    deq = deque()
    for q in range(len(b)):
        if deq and q - deq[0] > k:
            deq.popleft()
        while deq and b[deq[-1]] > b[q]:
            deq.pop()
        deq.append(q)

        if b[q] - b[deq[0]] > maxSum:
            maxSum = b[q] - b[deq[0]]
    return maxSum
print(maxSubseq([8, -1, -1, 4, -2, -3, 5, 6, -3], 8))