Can't implement Maximal subarray with length constraint algorithm

Question

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

B[] should be [8, 7, 6, 10, 8, 5, 10, 16, 13] and the same size as A[]. — aropan
– aropan, Commented Nov 8, 2021 at 17:13
@aropan tried it yesterday too, the result is still print(maxSubseq([8, -1, -1, 4, -2, -3, 5, 6, -3], 8)) == 11 — Evgeny
– Evgeny, Commented Nov 8, 2021 at 17:39
With your code, you miss the subarray containing just the first element. You miss the subarray [8] in A[] because you start with b = [a[0] + a[1]] rather than b=[a[0]]. That is why you have different length for A[] and B[]. — sfx
– sfx, Commented Nov 8, 2021 at 20:23

adarsh · Accepted Answer · 2021-11-09 11:08:41Z

0

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))

edited Nov 9, 2021 at 11:08

answered Nov 8, 2021 at 20:41

adarsh

14213 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Devd · Accepted Answer · 2022-10-25 05:47:24Z

0

Java Implementation

class HelloWorld {
public static void main(String[] args) {
    int[] arr = {8, -1, -1, 4, -2, -3, 5, 6, -3};
    int k = 8;
    
    int[] prefixSum = new int[arr.length+1];
    for(int i=0; i<arr.length; i++){
        prefixSum[i+1] = prefixSum[i] + arr[i];
    }
    
    Deque<Integer> dq = new ArrayDeque<>();
    int maxSum = 0;
    for(int i=0; i<prefixSum.length; i++){
        if(!dq.isEmpty() && i-dq.peekFirst() > k){
            dq.pollFirst();
        }
        
        while(!dq.isEmpty() && prefixSum[dq.peekLast()] > prefixSum[i]){
            dq.pollLast();
        }
        
        dq.addLast(i);
        
        if(prefixSum[i] - prefixSum[dq.peekFirst()] > maxSum){
            maxSum = prefixSum[i] - prefixSum[dq.peekFirst()];
        }
    }
    
    System.out.println(maxSum);
}}

answered Oct 25, 2022 at 5:47

Devd

11 bronze badge

1 Comment

rainbow.gekota Over a year ago

The question is tagged with python :/

Collectives™ on Stack Overflow

Can't implement Maximal subarray with length constraint algorithm

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related