Maximum non-negative subarray

class Solution:
    # @param A : list of integers
    # @return a list of integers
    def maxset(self, A):
        i = 0
        af = []
        a1 = []
        while i < len(A):
            if A[i] >= 0:
                a1.append(A[i])
            else:
                af.append(a1)
                a1 = []
            i += 1
        
        # Append the last subarray, if any
        af.append(a1)
        
        # Find a set of all sums of all sub-arrays, rest is self-explanatory
        b = [sum(i) for i in af]

        mx = max(b)
        ind = b.index(mx)
        return af[ind]

Runs in O(n) time complexity and O(n) space complexity. 
This method is a bit crude, but is clean and easy to follow.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s