走査アルゴリズムは連続サブベクトルの最大と問題を解く(Python)

前編では有限状態機で解きましたが、実はスキャンをしました.ただ、問題を複雑に考えました.
スキャンについては、まず自分に3つの質問をすると思います.
1.スキャン方法(配列要素を巡回)
2.スキャンごとに何が変わるか(ここのアルゴリズムはmaxendinghereを変え、前編のアルゴリズムは状態を変える)
3.変更されたものは結果に影響しますか(maxendinghereがmaxsofarより大きい場合、maxsofarはmaxendinghereに割り当てられます)
問題を考える方法によって異なる解決策を導入し、その差が大きすぎる!!前編では正負号に注目しすぎて、シーケンスセグメントを採用し、状態遷移の方法で問題を解決しました.ここでの解法は最大和,および最大和に影響を及ぼす可能性のある因子,maxsofarとmaxendinghereの相対的な大きさに注目する.時間の複雑さはすべてO(n)ですが、高下立現!
コードは次のとおりです(python).
 

#!/usr/bin/python                                                                                                                                                      

def scan(vector):               # return (maxsofar, low, high)                                                                                                         
    length = len(vector)
    maxsofar = 0
    maxendinghere = 0
    low = 0
    high = 0
    low2 = 0
    high2 = 0
    for i in range(0, length):
        if maxendinghere + vector[i] > 0:
            maxendinghere = maxendinghere + vector[i]
            high2 = i+1
        else:
            maxendinghere = 0
            low2 = i+1
        if maxsofar >= maxendinghere:
            high = high
            low = low
            maxsofar = maxsofar
        else:
            high = high2
            low = low2
            maxsofar = maxendinghere
    return (maxsofar, low, high)

def test():
    vector = [-1, -1, -1, -1]
    (maxsofar, low, high) = scan(vector)
    print vector
    print maxsofar, low, high
    print

    vector = [1, -1, -1, -1]
    (maxsofar, low, high) = scan(vector)
    print vector
    print maxsofar, low, high
    print

    vector = [-1, -1, -1, 1]
    (maxsofar, low, high) = scan(vector)
    print vector
    print maxsofar, low, high
    print

    vector = [-1, 2, 3, -4]
    (maxsofar, low, high) = scan(vector)
    print vector
    print maxsofar, low, high
    print

    vector = [1, 2, 3, 4]
    (maxsofar, low, high) = scan(vector)
    print vector
    print maxsofar, low, high
    print

    vector = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
    (maxsofar, low, high) = scan(vector)
    print vector
    print maxsofar, low, high
    print

def main():
    test()

if __name__ == '__main__':
    main()

実行結果:
root@localhost :/home/James/mypro/Python# ./scan.py [-1, -1, -1, -1] 0 0 0
[1, -1, -1, -1] 1 0 1
[-1, -1, -1, 1] 1 3 4
[-1, 2, 3, -4] 5 1 3
[1, 2, 3, 4] 10 0 4
[31, -41, 59, 26, -53, 58, 97, -93, -23, 84] 187 2 7
root@localhost :/home/James/mypro/Python#
 
後記:pythonは本当にこのような小さなdemoを書くのに適しているような気がします.速くて便利です.