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.

Leave a comment