python求解最大子序列问题，子序列可连续或不连续

最大子序列问题在笔试中已经遇上过很多次了，今天只是想简单的总结一下，最大子序列主要分为两种类型：一种是子序列可以不连续的最大子序列和（这个比较简单，思路就是累加非负数即可）、另一种是子序列必须连续的最大子序列和（这个稍微复杂是一个动态规划问题），下面就简单就这两种问题做一下总结，具体看如下实现：

#!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]