CODEWITHSUNDEEP
pythonsub-array
Krishna Vamshi Chintala
Krishna Vamshi Chintala

Reputation: 31

Finding Maximum non-negative Subarray in python

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?

Upvotes: 1

Views: 1519

Answers (2)

Rahil Sayed
Rahil Sayed

Reputation: 1

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

Upvotes: 0

Mark
Mark

Reputation: 92461

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)

Upvotes: 3

Related Questions