下面的代码实现了O(n ^ 2)的时间复杂度.我希望能够在O(n)中完成.
例如,给定数组[-2,1,-3,4,-1,2,1,-5,4],连续子阵列[4,-1,2,1]具有最大的和= 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