# Find max non-negative sub array from a given array [closed]

Task : Find out the maximum sub-array of non negative numbers from an array. The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid. Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

Note: If there is a tie then compare the segment length's and return segment which has maximum length.

Code:

def maxset(array):
"""Returns maximum sub array of non-negative numbers"""
sum = 0
current_sum = []
count = 0
sub_array = []
sub_array_list = []

for i in range(len(array)):
if array[i] >= 0:
sum = sum + array[i]
sub_array.append(array[i])

else:
current_sum.append(sum)
sub_array_list.append(sub_array)
sum = 0
sub_array = []
count += 1

if count == 0:
return sub_array
max_sum = max(current_sum)
if max_sum > sum:
i= current_sum.index(max_sum)
return sub_array_list[i]
elif max_sum < sum:
return sub_array
elif max_sum == sum:
if len(sub_array) > len(max(sub_array_list,key=len)):
return sub_array
else:
return max(sub_array_list,key=len)


Test cases :

def main():
print maxset([ 336465782, -278722862, -2145174067, 1101513929, 1315634022, -1369133069, 1059961393, 628175011, -1131176229, -859484421 ])
print maxset( [ 756898537, -1973594324, -2038664370, -184803526, 1424268980 ] )
print maxset( [ 1, 2, 5, -7, 2, 5 ] )
print maxset( [ 1, 2, 5, -7, 2, 5 ] )
print maxset( [ 222])
print maxset( [ 1, 1])
print maxset( [  3, -1, 1, 1, 1, -1, 3])
if __name__ == '__main__':
main()


How can i make this code more efficient?

• This does not run, apparently the indentation is wrong. – Martin R May 6 '18 at 10:01
• Calling maxset( [ 1, 1 ]) results in a “ValueError: max() arg is an empty sequence” – Martin R May 6 '18 at 10:27
• maxset([ 3, -1, 1, 1, 1, -1, 3 ]) returns . The correct result would be [1, 1, 1] because it has the same sum but a greater length. – Martin R May 6 '18 at 10:29
• @MartinR I have edited the code to include test cases pointed out by you – Latika Agarwal May 6 '18 at 13:10
• Still does not work correctly for maxset( [ 3, -1, 1, 1, 1, -1, 2 ]) – Martin R May 6 '18 at 13:35

The first thing that I would suggest is replacing

for i in range(len(array)):
if array[i] >= 0:
sum = sum + array[i]
sub_array.append(array[i])


with something like the following:

i = 0
for elem in itertools.chain(array, [-1]):
if elem >= 0:
sum = sum + elem
sub_array.append(elem)
...
i += 1


The purpose of itertools here is just to simplify the code by adding a fencepost value: if you guarantee that the last thing you see will be negative you don't need any special case handling to check the last run of positives.

(You would need to import itertools)

The second thing I would do is avoid slowly building arrays. You construct sub_array one element at a time as you go through the contiguous positive bit of the array. It would be more efficient to just store the start index and wait until the end of the contiguous positive bit of the array. To get it out as a list in its own right, use python's slices notation. (i.e. array[start:stop])

The third thing I would change is avoid building arrays (almost) altogether. The most efficient work is the work you don't do. Instead of building all the candidates for checking later, and storing them all in sub_array_list, just hold the start and end indices of whichever sub array is currently in the lead.

Do remember your tie-breaker condition when calculating "in the lead". (The built in < operator on tuples is good for tie breaker cases: (a, b) < (c, d) is True if a < c or a == c and b < d.

• I have just realised that my original implementation with the chain was wrong; that loop goes over indices rather than over the elements. I was originally going to suggest changing that loop, and forgot I hadn't! I have edited my answer. – Josiah May 6 '18 at 17:15