918. 环形子数组的最大和(Python)

难度:★★★☆☆
类型:数组
方法:动态规划

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个由整数数组 A 表示的环形数组 C,求 C 的非空子数组的最大可能和。

在此处,环形数组意味着数组的末端将会与开头相连呈环状。(形式上,当0 <= i < A.length 时 C[i] = A[i],且当 i >= 0 时 C[i+A.length] = C[i])

此外,子数组最多只能包含固定缓冲区 A 中的每个元素一次。(形式上,对于子数组 C[i], C[i+1], ..., C[j],不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length)

示例 1:

输入:[1,-2,3,-2]
输出:3
解释:从子数组 [3] 得到最大和 3

示例 2:

输入:[5,-3,5]
输出:10
解释:从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3:

输入:[3,-1,2,-1]
输出:4
解释:从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

示例 4:

输入:[3,-2,2,-3]
输出:3
解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

示例 5:

输入:[-2,-3,-1]
输出:-1
解释:从子数组 [-1] 得到最大和 -1

提示:

-30000 <= A[i] <= 30000
1 <= A.length <= 30000
通过次数7,230提交次数21,014

解答

我们先来回顾一下非环形的情况,或者说53题最大子序和的问题。使用动态规划可以方便的解决。

【数组定义】定义数组dp,长度与输入数组nums一致,dp[i]表示以nums[i]结尾的子数组中和最大的连续子数组。

【初始情况】当i=0时,子数组nums[:i+1]中只有一个元素,直接将nums[0]赋值给dp[0]即可。

【递推公式】
对于i位置处的情况,有两种可能性,一种是从dp[i-1]继承过来,也就是nums[i]被添加到以nums[i-1]结尾的子数组中,将原先的子数组做了延长;另一种情况就是原先的子数组到此位置,nums[i]成为新的子数组的开头。我们选取这两种情况的子数组的最大值,填充在当前位置i即可。

dp[i]=max(dp[i-1]+nums[i],nums[i])

【最终返回值】

最终返回dp数组中的最大值即可。

class Solution:
    def maxSubArray(self, nums):
        size = len(nums)
        if size == 0:
            return None
        if size == 1:
            return nums[0]

        dp = [False for _ in range(size)]  # 记录状态:当前以i结尾的最大值记录在里面
        dp[0] = nums[0]

        for i in range(1, size):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])  # 记录最大状态
        return max(dp)

现在的情况是,原始数组首尾连接,形成环形,这样一来,我们就需要考虑另外一种情况,也就是尾部一段连接开头一段的情况。我们从相反的角度来思考这种情况。假设数组被分成了ABC三段,能够使得子数组的和最大的是C+A段,注意A段和C段在表达形势上是断开的,但是在物理意义上是连续的,那么对于剩下的中间的B段,在形势上就是连续的,而且这种状况下,B段的和是最小的。如果我们能够找到最小和的连续子数组,就从另一个角度确定了最大和的连续子数组(剩下的那两部分就是),问题就转化为,如何找到非环形列表的最小和的连续子数组。很显然,我们可以用与上述类似的动态规划的方法来解决。

这里就不再使用数组了,因为我们只关心当前最新的最佳结果,因此可以降低一下空间复杂度,cur_min和res_min分别代表当前子数组最小值,以及研究到现在为止的最佳结果。遍历数组,对于当前元素num,递推公式为cur_min = min(num+cur_min, num),并且用res_min及时记录最新结果。当我们找到了最小和的连续子数组,那么剩下的两部分就组成了最大和的连续子数组,其和就是sum(A) - res_min。

综上,根据最大和的连续子数组在形式上是连续的或者断开的,这两种情况选其最优即可。需要补充的是,这里需要判断数组元素全部为负数的情况,这时直接返回最大值。

class Solution:
    def maxSubarraySumCircular(self, A):
        res = cur = 0
        for num in A:
            cur = max(cur+num, num)
            res = max(res, cur)

        if res == 0:
            res = max(A)
            return res

        cur_min = res_min = 0
        for num in A:
            cur_min = min(num+cur_min, num)
            res_min = min(res_min, cur_min)

        res = max(res, sum(A) - res_min)
        return res

如有疑问或建议,欢迎评论区留言~

有关更多力扣中等题的python解决方案,请移步力扣中等题解析

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 217,907评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,987评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,298评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,586评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,633评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,488评论 1 302
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,275评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,176评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,619评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,819评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,932评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,655评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,265评论 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,871评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,994评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,095评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,884评论 2 354

推荐阅读更多精彩内容