python官方题解--连续子数组的最大和
连续子数组的最大和
http://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
时间复杂度O(N)
空间复杂度O(1)
动态规划:
> dp[i] = dp[i-1] + p[i] # if i != 0 and dp[i-1] > 0 > dp[i] = p[i] # if i == 0 or dp[i-1] < 0
代码:
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
if not array:
return None
maxNum = array[0]
for i in range(1,len(array)):
if array[i-1] > 0:
array[i] = array[i-1] + array[i]
maxNum = max(maxNum, array[i])
return maxNum
