最大子序列問題在筆試中已經遇上過很多次了，今天只是想簡單的總結一下，最大子序列主要分為兩種類型：一種是子序列可以不連續的最大子序列和（這個比較簡單，思路就是累加非負數即可）、另一種是子序列必須連續的最大子序列和（這個稍微復雜是一個動態規劃問題），下面就簡單就這兩種問題做一下總結，具體看如下實現：
#!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]
