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)

私はアルゴリズムを学んでいます (Book: Introduction to Algorithms)..だから、最大合計を構成する与えられた配列のサブ配列を見つけることになっています..ええ、非再帰的、線形時間アルゴリズム..

これは私がやったことです（上に表示）..しかし、私の解決策では、forループ内にforループがあり、両方とも「n」項を繰り返します..

私が間違っていなければ、O(n^2)どちらが直線的ではないはずです! その場合、どのように解決すればよいのでしょうか。

4

2 に答える 2

5

これは確かに直線的な解決策ではありません。この問題を解決する線形時間アルゴリズムの 1 つは、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) であり、j ループの内側にある i ループにあります。

しかしArrayTot(arr, i, j)、合計配列、つまり range_sum[1..n] を使用して O(1) にrange_sum[1] = arr[1]最適化range_sum[i+1] = range_sum[i] + arr[i+1], i>0できArrayTot(arr, i, j)ますrange_sum[j]-range_sum[i-1]。

しかし、あなたのメソッドではまだ O(n) を取得できません。これは非常に古典的な DP 問題です。Google で検索してください。

于 2012-10-02T17:06:07.450 に答える