2
votes

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
1

1 Answers

6
votes

Familiarize yourself with Kadane's Algorithm. Achieved time complexity is O(n).

def Maximum_Sub_Array(arr, n):
    ans = 0
    _sum = 0
    num_of_neg_values = 0
    for i in range(n):
        if arr[i] < 0:
            num_of_neg_values += 1
        if (_sum + arr[i] > 0):
            _sum += arr[i]
        else:
            _sum = 0
        ans = max(_sum, ans)
        if num_of_neg_values == n:
            return max(arr)
    return ans