python - 具有最大和的数组(至少包含一个数字)中的连续子数组

Question

下面的代码实现了 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

Answer 1

熟悉 Kadane 的算法。实现的时间复杂度为 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