Finding Maximum non-negative Subarray in python

Question

I've tried to find the sub-array(s) from a given which contain elements of maximum sum than any other sub array.

Below function has parameter as input a and the output needs to be returned. There can be more than one subarray as their maximum sum can be equal. The code did not seem to be working as expected.

def max_sum_subarray(a):
        N, sub_sum, max_sum, subArrays = len(a), 0, 0, {}
        p,q=0,0    #starting and ending indices of a max sub arr

        for i in range(N):
            q=i
            sub_sum+=a[i]

            if(a[i]<0):
                q-=1
                if(sub_sum>=max_sum):
                    if(sub_sum>max_sum):
                        subArrays.clear()
                        subArrays[sub_sum]=[(p,q)]
                    else:
                        subArrays[sub_sum].append((p,q))

                sub_sum=0
                p=i+1

        if(sub_sum>=max_sum):
            if(sub_sum>max_sum):
                subArrays.clear()
                subArrays[sub_sum]=[(p,q)]
            else:
                subArrays[sub_sum].append((p,q))
        return(subArrays[p:q+1])

When I tried to run for input

a=[ 1, 2, 5, -7, 2, 5 ]

Expected output is [1, 2, 5] but it gave [2, 5] instead. Can anyone please post the solution in python?

subArrays is a dict, when running your code I get TypeError: unhashable type: 'slice' on the return line... — Adam.Er8
– Adam.Er8, Commented Jul 14, 2019 at 7:26
Aproach is, start from the first index and keep on adding the sum until you find a negative element, from now on start adding the sum from zero, but also maintain the maximum sums. Here, I created a dictionary updating key as so far maximum sum and value as so far required sub-array's starting and ending index. — Krishna Vamshi Chintala
– Krishna Vamshi Chintala, Commented Jul 14, 2019 at 7:29

Mark · Accepted Answer · 2019-07-14 07:40:45Z

3

It seems like you making this harder than necessary. You can just keep track of max array seen to far and the current one you're pushing into -- you don't really need to care about anything else. When you hit a negative (or the end of the array) decide if the current should be the new max:

def maxSub(a):
    max_so_far = []
    max_sum = 0
    cur = []
    for n in a:
        if n >= 0:
            cur.append(n)
        else:
            cur_sum = sum(cur)
            if cur_sum > max_sum:
                max_sum = cur_sum
                max_so_far = cur
            cur = []

    return max([max_so_far, cur], key = sum)


a=[ 1, 2, 5, -7, 2, 5 ]

maxSub(a)
# [1, 2, 5]

Of course itertools.groupby makes this a one-liner:

from itertools import groupby

a=[ 1, 2, 5, -7, 2, 5 ]
max([list(g) for k,g in groupby(a, key=lambda x: x>0) if k == True], key=sum)

answered Jul 14, 2019 at 7:40

Mark

92.7k8 gold badges116 silver badges156 bronze badges

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

8 Comments

Radosław Cybulski Over a year ago

I like groupby approach. Also you don't need cur list, just remember first positive index and go cur_sum = sum(a[firstPositive:n]), performance will be actually even faster.

Mark Over a year ago

Yeah, that's a good tip @RadosławCybulski — thanks. Never sure how to balance clarity of concept and efficiency on answers here.

Radosław Cybulski Over a year ago

The same here, obvious things for me doesn't seem so obvious after i type it. This is actually why i like answering on SO, as it forces me to rethink everything i write in context of reader.

Shantanu Gupta Over a year ago

This will accept form some TC's only. for TC [ 0, 0, -1, 0] expected op is 0 0 and it gives just 0 so for this use Sliding windows concept.

Mark Over a year ago

@ShantanuGupta is the sum of [0, 0] greater than the sum of [0]? Why is one preferred over the other?

|

Rahil Sayed · Accepted Answer · 2021-06-24 14:05:31Z

For the following conditions:

NOTE 1: If there is a tie, then compare with segment’s length and return segment which has maximum length

NOTE 2: If there is still a tie, then return the segment with minimum starting index

Here is my working code in python:

def check(max_arr,curr):
    if sum(curr) > sum(max_arr):
        max_arr = curr
    elif sum(curr) == sum(max_arr):
        if len(curr) > len(max_arr):
            max_arr = curr
        elif len(curr) == len(max_arr):
            if max_arr and (curr[0] > max_arr[0]):
                max_arr = curr
    return max_arr

def maxset(A):
    curr = []
    max_arr = []
    for i in A:
        if i >= 0:
            curr.append(i)
        else:
            max_arr = check(max_arr,curr)
            curr = []
    max_arr = check(max_arr,curr)                    
    return max_arr

Collectives™ on Stack Overflow

Finding Maximum non-negative Subarray in python

2 Answers 2

8 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related