问题描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
示例
————————————————————————————————
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
————————————————————————————————
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路
典型的动态规划问题
状态方程：max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )
意义是：从头开始遍历数组，遍历到数组元素 arr[ i ] 时，连续的最大的和可能为 max( dp[ i -1 ] ) + arr[ i ] ，也可能为 arr[ i ] ，做比较即可得出哪个更大，取最大值。时间复杂度为 n
编码实现
#!usr/bin/env python
#encoding:utf-8
def test_func(arr):
'''
求连续子数组的最大和
'''
tmp=0 #临时最大值
res=-1000000 #比较之后的最大值
for i in range(len(arr)):
tmp=max(arr[i],tmp+arr[i]) #状态方程
res=max(res,tmp)
print res
if __name__ == '__main__':
arr = [-1,2,1,3,4,16,7,-30,12,3]
test_func(arr)
