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

连续子数组的最大和(二)

https://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21

class Solution:
    def FindGreatestSumOfSubArray(self, array: List[int]) -> List[int]:
        # write code here
        dp = [0 for i in range(len(array))]
        dp[0] = array[0]
        maxsum = dp[0]
        # 滑动区间
        left = 0
        right = 0
        # 记录最长的区间
        resl = 0
        resr = 0
        for i in range(1,len(array)):
            if dp[i-1]+array[i]>=array[i]:
                dp[i] = dp[i-1]+array[i]
                right = i
                thissum = dp[i]
                if thissum>=maxsum:
                    maxsum = thissum
                    if right-left>resr-resl:
                        resl = left
                        resr = right
            else:
                dp[i] = array[i]
                left = i
                right = i
                thissum = dp[i]
                if thissum>maxsum:
                    maxsum = thissum
                    resl = left
                    resr = right
                elif thissum==maxsum:
                    if right-left>resr-resl:
                        resl = left
                        resr = right
        
        return array[resl:resr+1]

全部评论

相关推荐

不对是145个人…嗯… 大家都没发现秋招提前批来了嘛..笑死我了
牛客39712426...:投了也是浪费时间,之前投米实习,除了浪费我时间写笔试题没有任何反馈,懒得投了
26届校招投递进展
点赞 评论 收藏
分享
06-26 17:24
已编辑
宁波大学 golang
迷失西雅图:别给,纯kpi,别问我为什么知道
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务