最大子配列と――動的計画法

3518 ワード
python
1、前の方法をまとめる
前回の解の最も大きい子の配列は暴力の解法を求めて、すべての可能な子の配列と求めて、それから比較して最大の子の配列と、この方法も最も考えやすくて、プログラミングは比較的に容易で、興味のある学生は私の前の博客を見ることができます.
2、動的計画に基づく最大サブ配列の和を求める問題
暴力解の複雑さはO(n**3)であるため,確かに少し大きいが,動的計画法を用いて解くことができ,主な構想も簡単明瞭である.最大和サブ配列は2つの部分から構成されていると仮定する.1つは順方向とsumであり,もう1つは順方向とsumの次の要素であり,sumの値が0未満であると最大サブ配列の一部になることは不可能であるため,以前のsumを捨てなければならない.新しいsumを再定義します.このsumの開始要素は、前のsumとシーケンスの次の要素です.動的計画法は簡潔明瞭で,時間的複雑さはO(n)にすぎず,解の回数を減らした.
3、コードサンプル
arr = [1,-2,3,4,-5]
def fun(arr):
    sum = arr[0]
    max = 0
    x = 0
    y = 0
    for i in range(1,len(arr)):

        if sum >= 0:
            sum += arr[i]
        else:
            sum = arr[i]
            x = i
        if sum > max:
            max = sum
            y = i
    if x>y:
        return arr[0:1]
    else:
        return arr[x:y+1]
if __name__=="__main__":
    print(fun(arr))
Socketプログラミング基盤:TCPプロトコルに基づくネットワークプログラミング
第七課:コンピュータネットワーク性能