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

# 用动态规划求一个连续数组最大和的时候，是一个dp数组，这个数组里面最大值才是最大和，
# 那么问题是如何根据这个dp最长子数组呢？
# 方法如下：
# 在求得dp的同时记录当前的dp的数组范围
# 如果当前dp是单个元素则要重置索引，
# 如果当前dp是最大值则要把当前索引保存起来为最大长度和最大索引范围，
# 特殊情况是如果当前dp是已经存在的最大值，
# 则需要考虑当前索引范围是否大于最大索引范围，如果是则更新

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        # write code here
        dp = [i for i in array]#初始化一个和原数组一样大的dp数组
        maxLen = 1 #最小数组长度为1
        start,end = 0,1 
        max_start,max_end = 0,1 
        maxSum = dp[0] 
        for i in range(1,len(array)):
                end +=1
                dp[i] = max(dp[i-1]+array[i], array[i])
                if dp[i-1]+array[i] < array[i]:
                        start,end = i,i+1
                if dp[i] > maxSum or (dp[i] == maxSum and (end - start ) > maxLen):
                        max_start = start
                        max_end = end
                        maxLen = end - start
                        maxSum = dp[i]
        return array[max_start:max_end]

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        # write code here
        # dp = [i for i in array]#初始化一个和原数组一样大的dp数组
        preval,curval = array[0],array[0]
        maxLen = 1 #最小数组长度为1
        start,end = 0,1 
        max_start,max_end = 0,1 
        maxSum = curval 
        for i in range(1,len(array)):
                end +=1
                curval = max(preval+array[i], array[i])
                if preval+array[i] < array[i]:
                        start,end = i,i+1
                if curval > maxSum or (curval == maxSum and (end - start ) > maxLen):
                        max_start = start
                        max_end = end
                        maxLen = end - start
                        maxSum = curval
                preval = curval
        return array[max_start:max_end]