python連続サブシーケンスの最大化と問題(ダイナミックプランニング)

説明:サブリストとは、リスト内のインデックス(下付き)が連続する要素からなるリストを指す.リストの要素はintタイプで、正の整数、0、負の整数を含む可能性があります.プログラム入力リストの要素、出力サブリストの要素の合計の最大値、例えば:入力:1-2 3 5-32
出力:8
入力:0-2 3 5-1 2
出力:9
入力:-9-2-3-5-3
出力:-2
問題として、元のリストaについて、要素a[i]が求められたサブリストの最後の要素であると仮定すると、求められたサブリストには、1)a[i]以前の要素2を含まない)a[i]以前のシーケンス(このシーケンスは前に累積して得られる)が含まれているため、解の過程は、リスト内の各要素について上記の仮定を行い、それぞれ2つの状況を解き、記録最大値を比較することである.
具体的には、時間的複雑度O(n)、空間的複雑度O(1):

def maxSubList(items):
    size = len(items)
    _sum = _max = items[0]
    for i in range(1, size):
        #                 （           ）
        _sum = max(0, _sum)
        _sum += items[i]
        #          
        _max = max(_sum, _max)
    return _max

def main():
    items = list(map(int, input().split()))
    result = maxSubList(items)
    print(result)

if __name__ == '__main__':
    main()

問題が与えられたシーケンスの先頭と末尾がつながっている場合(すなわち1つの環状を構成する)を考慮すると,問題は2つの場合に分けられる:1)求めたサブシーケンスが先頭と末尾を越えない場合,問題は最初に提案したものと一致し,上記の方法で解くことができる.2)求めるサブシーケンスが先頭にまたがる,すなわち排除されたシーケンスが必ず先頭にまたがらない,排除されたシーケンスを解くことによって結果を求める,この場合問題は状況1)の逆問題となる:「サブシーケンスの最小和を解く」,総シーケンスと最小シーケンスを減算すること,すなわち求めた結果である.
次のようになります.

def maxSubList(items):
    size = len(items)
    _sum = _max = items[0]
    for i in range(1, size):
        _sum = max(0, _sum)
        _sum += items[i]
        _max = max(_sum, _max)
    return _max

def minSubList(items):
    size = len(items)
    _sum = _min = items[0]
    for i in range(1, size):
        _sum = min(0, _sum)
        _sum += items[i]
        _min = min(_sum, _min)
    return _min

def main():
    items = list(map(int, input().split()))
    result = max(maxSubList(items), sum(items) - minSubList(items))
    print(result)

if __name__ == '__main__':
    main()