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