【剑指offer】＜动态规划--中等＞【JZ85 连续子数组的最大和(二)】

注意

可以使用以下测试案例来检验：

[0,0,0,1,1,-51,0,0,1,1]

正确答案应该是 [0,0,0,1,1]，但是其他方法结果都是[0,0,1,1]

v1 – dp

本解法比较易懂，但是内存速度开销会稍微大一点。 但是目前看下来，只有本解法才是正确的。

分析

该题目与之前做过的连续子序列最大和很相似，唯一的区别是需要返回子序列是什么
这样只需要新增两个参数来记录子序列的起始即可
然而，题目给定了一种特殊情况，就是

如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个

由于增加了这个约束，使得我们不得不记录当前最长的序列长度是多少。下面看看我们在代码中如何处理

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        maxSum, nSum, sBegin, sEnd, nBegin, nEnd = -1000, -100, 1, 1, 1,1
        # maxSum 最大值, nSum当前累加和， sBegin,sEnd: 最长序列起点、终点 ； nBegin,nEnd: 当前序列起点、终点
        for i in range(len(array)):
            if nSum >= 0:   # 确保前面累加的sum等于0的部分可以保留下来，使得序列尽可能长。
                nSum = nSum + array[i]
                if nSum >= maxSum:  #当前和大于最大的情况，则需要把这个点加进来
                    maxSum = nSum
                    nEnd = i
                    #若序列超过了最长序列（并且当前nSum>=maxSum)，则更新最长序列
                    if sEnd-sBegin <= nEnd-nBegin:                           
                    	sBegin, sEnd = nBegin, nEnd
            elif nSum < 0:  # 若左边的求和已经小于0了，则丢弃之前的序列
                nSum = array[i]
                nBegin, nEnd = i, i
                if nSum > maxSum: # 当前和大于最大和 的情况， 则需要更新序列
                    maxSum = nSum
                    sBegin, sEnd = nBegin, nEnd
        return array[sBegin:sEnd+1]

v2(AC, but error)

最常见的解法，只考虑尽可能大，但是没有考虑相同值，但是长度不一的情况；若遇到和相同，则只会选择相对位置靠后的子序列。

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        maxval = array[0]
        temp = array[0]  # 序列累加
        endindex = 1
        beginindex = 0
        for i in range(1, len(array)):
            if temp < 0:
                temp = array[i]
                beginindex = i
            else:
                temp += array[i]
            if temp >= maxval:
                endindex = i
                maxval = temp
        # begin > end 表示 序列全为负
        # begin不断累加， 但此时end已保存最大值索引
        if beginindex > endindex:
            return array[endindex:endindex + 1]
        return array[beginindex:endindex + 1]