0 
# given an array, it solves sum of elements in it, 
# args: array, initial and final indices
# Returns: sum of elements
def ArrayTot (arr, low, high):
    return sum( arr[low : high+1] )

# Is this linear time?
# args: array, initial and final indices
# returns: Max possible value in sub-array.
def MaxSubArray (arr, low, high):
    # max value of sub-array
    TotalArray = 0
    # starts iterating arr from left - right i.e., arr[low, j]
    for j in xrange(low, high+1):
        # finds sum of sub array arr[low,j]
        tot = ArrayTot (arr, low, j)
        # Iterates the sub-array arr[low,j] so as to find any other possible arr[i,j] which results max value
        for i in xrange(low, j+1):
            SubArrTot = ArrayTot(arr, i, j)
            if SubArrTot >= tot:
                tot = SubArrTot
        if tot >= TotalArray:
            TotalArray = tot
    return TotalArray

arr = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
low = 0
high = 15

print MaxSubArray(arr, low, high)

我正在学习算法（书：算法简介）。所以，我应该在给定数组中找到一个构成最大和的子数组。是的，一个非递归的线性时间算法。

这就是我所做的（如上所示）。但是在我的解决方案中，for循环中有一个for循环，并且都迭代了“n”项。

如果我没记错的话，应该是O(n^2)哪个不是线性的！在那种情况下，我应该如何解决它？

4

2 回答 2

5

这当然不是线性解决方案。解决这个问题的线性时间算法之一被称为Kadane 算法。

哪怕只是这一段代码

for j in xrange(low, high+1):
    tot = ArrayTot (arr, low, j)

已经有Theta(n^2)时间复杂度了。

于 2012-10-02T16:54:25.777 回答
2

恐怕它甚至不是 0(n^2).. 它是 O(n^3)。ArrayTot(arr, i, j)是 O(n)，并且它在 i-loop 中，它在 j-loop 内部。

但是你可以ArrayTot(arr, i, j)使用求和数组优化到 O(1)，即 range_sum[1..n]，其中range_sum[1] = arr[1], range_sum[i+1] = range_sum[i] + arr[i+1], i>0，那么我们可以ArrayTot(arr, i, j)在 O(1) 时间内计算，只需使用range_sum[j]-range_sum[i-1].

但是你的方法仍然无法得到 O(n)，这是一个非常经典的 DP 问题，只需 google 即可。

于 2012-10-02T17:06:07.450 回答