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

题目：https://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        # write code here
        everymaxsum=array[0]
        allmax=array[0]
        left=0
        right=0
        #记录最长的区间
        resl=0
        resr=0
        everymaxsum_next=everymaxsum
        allmax_next=allmax
        for i in range(1,len(array)):
            right=right+1#不管everymaxsum+array[i],array[i]谁大谁小，都要移动right
            everymaxsum=everymaxsum_next
            everymaxsum_next=max(everymaxsum+array[i],array[i])
            #everymaxsum因为下面要用到比较，所以不能像原来一样写everymaxsum=max(everymaxsum+array[i],array[i])，不能把everymaxsum覆盖
            if everymaxsum+array[i]<array[i]:
                left=right
                                
            allmax=allmax_next
            allmax_next=max(everymaxsum_next,allmax)
            #allmax同理，不能写allmax=max(everymaxsum_next,allmax)
            if  everymaxsum_next>allmax:
                resl=left
                resr=right
            elif everymaxsum_next==allmax and (right-left)>(resr-resl):
                resl=left
                resr=right

        res=array[resl:resr+1]
        return res