This is a typical interview question:
Given an array that contains both positive and negative elements without 0, find the largest subarray whose sum equals 0.
I am not sure if this will satisfy all the edge case. If someone can comment on that, it would be excellent. I also want to extend this to sum equaling to any , not just 0. How should I go about it? And any pointers to optimize this further is also helpful.
from collections import Counter
def sub_array_sum(array,k=0):
start_index = -1
hash_sum = {}
current_sum = 0
keys = set()
best_index_hash = Counter()
for i in array:
start_index += 1
current_sum += i
if current_sum in hash_sum:
hash_sum[current_sum].append(start_index)
keys.add(current_sum)
else:
if current_sum == 0:
best_index_hash[start_index] = [(0,start_index)]
else:
hash_sum[current_sum] = [start_index]
if keys:
for k_1 in keys:
best_start = hash_sum.get(k_1)[0]
best_end_list = hash_sum.get(k_1)[1:]
for best_end in best_end_list:
if abs(best_start-best_end) in best_index_hash:
best_index_hash[abs(best_start-best_end)].append((best_start+1,best_end))
else:
best_index_hash[abs(best_start-best_end)] = [(best_start+1,best_end)]
if best_index_hash:
(bs,be) = best_index_hash[max(best_index_hash.keys(),key=int)].pop()
print array[bs:be+1]
else:
print "No sub array with sum equal to 0"
def Main():
a = [6,-2,8,5,4,-9,8,-2,1,2]
b = [-8,8]
c = [7,8,-1,1]
d = [2200,300,-6,6,5,-9]
e = [-9,-6,8,6,-14,9,6]
sub_array_sum(a)
sub_array_sum(b)
sub_array_sum(c)
sub_array_sum(d)
sub_array_sum(e)
if __name__ == '__main__':
Main()
