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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型一维数组
#
class Solution:
    def FindGreatestSumOfSubArray(self, array: List[int]) -> List[int]:
        # write code here
        # 初始化dp数组
        dp = [i for i in range(len(array))]

        # 定义初始化数组的俩组指针
        # 第一组指针是start,end,这组指针记录的是dp[i]的最大子序列的开始下标和结束下标
        start, end = 0, 1

        # max_start,max_end记录的是dp当前遍历到dpi的所有的最大子序列的开始下标和结束下标
        max_start, max_end = 0, 1

        dp[0] = array[0]

        maxsum = array[0]

        for i in range(1, len(array)):
            # dp方程，列出dp方程
            dp[i] = max(array[i] + dp[i - 1], array[i])
		    #统计下最大值在array[i] + dp[i - 1], array[i]俩个数之间
            sum = max(array[i] + dp[i - 1], array[i])
            
			# 更新下标，有2种情况，一种情况是dp[i]的前面最大子序列加i小于当前元素i，
            #此时需要更新start,end的值为当前元素
            
            if sum==array[i] and sum!=array[i]+dp[i-1]:
                start, end = i, i + 1
                
            
			# 另一种情况是dp[i]的前面最大子序列加i大
            #于当前元素i,此时end的值应该加1，将它囊括进去最新的元素
            else:
                end += 1
				
            # 更新完start,end后，如果start,end组成的和即dp[i]大于已经保存的最大值
            #，那么当前更新下Max_start,max_end

            if sum >  maxsum:
                max_start = start
                max_end = end
            # 如果相等，比较哪个长，元素多，换成哪个
            if sum ==maxsum:
                if len(array[start:end]) > len(array[max_start:max_end]):
                    max_start, max_end = start, end
            else:
                pass
            maxsum=max(sum,maxsum)
        # 待比较结束后，返回最大的列表
        return array[max_start:max_end]