题解 | #连续子数组的最大和#

def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
	# write code here
	maxSum = array[0]
	continuousSum = array[0]

	for i in range(1, len(array)):
		if continuousSum < 0 and array[i] > continuousSum:
			continuousSum = array[i]
		elif continuousSum + array[i] > 0:
			continuousSum += array[i]
		else:
			continuousSum = array[i]
		maxSum = max(maxSum, continuousSum)

	return maxSum

时间复杂度：O(n)

空间复杂度：O(1)

题目要求寻找子数组最大和，可以通过自底向上的动态规划思路来解决。我们先遍历整个数组，并将每一个元素与当下的和continuousSum相比较，如果continuousSum为负，那么存在一个最大和不包含continuousSum，因此抛弃continuousSum之前的值并将当前元素的值赋予continuousSum。反之如果当前元素与continuousSum的和为正，则最大和有可能包含之前的区间，所以我们继续将当前元素的值累积到continuousSum中。

需要注意的是，在每一步我们都需要更新maxSum的值。