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

def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
	# write code here
	maxSum, maxStart, maxEnd = array[0], 0, 0
	currSum, currStart, currEnd = array[0], 0, 0

	for i in range(1, len(array)):
		if currSum + array[i] >= array[i]:
			currSum += array[i]
			currEnd += 1
		else:
			currSum = array[i]
			currStart = i
			currEnd = i

		if currSum > maxSum:
			maxSum, maxStart, maxEnd = currSum, currStart, currEnd
		elif currSum == maxSum and maxEnd - maxStart <= currEnd - currStart:
			maxSum, maxStart, maxEnd = currSum, currStart, currEnd

	return array[maxStart: maxEnd + 1]  

时间复杂度：O(n)

空间复杂度：O(1)

题目要求寻找最大和子数组，解题思路与寻找子数组最大和相同。我们采取优化的动态规划方案，在每一次遍历中更新当前最大和子数组的区间即可。