pythonは最大のサブシーケンス問題を解き、サブシーケンスは連続的または不連続的であることができる.

最も大きなサブシーケンスの問題は筆記試験で何度も遭遇しましたが、今日は簡単にまとめたいだけです.最も大きなサブシーケンスは主に2つのタイプに分けられます.1つはサブシーケンスが不連続であることができる最も大きなサブシーケンスと(これは比較的簡単で、構想は非負の数を累積すればいい)、もう1つはサブシーケンスが連続しなければならない最も大きなサブシーケンスと(これは少し複雑で動的な計画問題です)、以下、この2つの問題について簡単にまとめ、具体的には以下のように実現します.

#!usr/bin/env python
#encoding:utf-8

'''
__Author__:    
  ：       
'''

def test_func(num_list):
    '''
               ，        
    （     if           ）
    '''
    length=len(num_list)
    dp=[0]*length
    dp[0]=num_list[0]
    for i in range(length):
        dp[i]=max(dp[i-1]+num_list[i], dp[i-1])
    print dp[-1]


def test_func2(num_list):
    '''
               ，       
    '''
    length=len(num_list)
    max_value=-10000000000
    tmp=0
    for i in range(length):
        tmp=max(tmp+num_list[i], num_list[i])
        max_value=max(max_value, tmp)
    print max_value


if __name__ == '__main__':
    num_list=[-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4]
    test_func(num_list)
    print '----------------------------------------------------'
    test_func2(num_list)

結果は以下の通りである.

97
----------------------------------------------------
78
[Finished in 0.3s]

もちろん、最も大きなサブシーケンスと問題は、最も大きなサブシーケンスの積問題に変換することもできます.