降低给定函数的时间复杂度[关闭]

Question

我试图降低以下函数的时间复杂度，但无法做到。 整数数组也可以有负数。

def solve(n, ar):
    max_sum_ending_here = 0  
    max_sum_so_far = 0       

    for end_index in range(n):
        for start_index in range(0, end_index + 1):
            max_sum_ending_here += ar[start_index]
            max_sum_so_far = max(max_sum_so_far, max_sum_ending_here)

    return max_sum_so_far

欢迎任何建议。

Answer 1

您似乎正在尝试使用嵌套循环查找最大子数组总和，这会导致时间复杂度为 O(n^2)，其中 n 是数组的大小。您可以使用 Kadane 算法将时间复杂度降低到 O(n)。方法如下：

def solve(n, ar):
    max_sum_ending_here = ar[0]  
    max_sum_so_far = ar[0]       

    for i in range(1, n):
        max_sum_ending_here = max(ar[i], max_sum_ending_here + ar[i])
        max_sum_so_far = max(max_sum_so_far, max_sum_ending_here)

    return max_sum_so_far

此版本迭代数组一次，维护两个变量：

max_sum_ending_here

跟踪以当前索引结尾的最大子数组总和，以及

max_sum_so_far

跟踪迄今为止看到的最大子数组总和。该算法的时间复杂度为 O(n)，效率更高。