The code below achieves the time complexity of O(n^2). I want to be able to do it in O(n).
For example Given the array [-2,1,-3,4,-1,2,1,-5,4] the contiguous subarray [4,-1,2,1] has the largest sum = 6.
def maximum_sub_array(arr, n):
ans = - sys.maxint - 1
for start_index in range(0, n):
_sum = 0
for sub_array_size in range(1,n+1):
if (start_index + sub_array_size > n): # Subarray exceeds array bounds
break
_sum += arr[start_index + sub_array_size -1] # Last element of the new Subarray
ans = max(ans, _sum)
return ans