難度：★★★☆☆
類(lèi)型：數(shù)組
方法：動(dòng)態(tài)規(guī)劃

題目

力扣鏈接請(qǐng)移步本題傳送門(mén)
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄

給定一個(gè)由整數(shù)數(shù)組 A 表示的環(huán)形數(shù)組 C，求 C 的非空子數(shù)組的最大可能和。

在此處，環(huán)形數(shù)組意味著數(shù)組的末端將會(huì)與開(kāi)頭相連呈環(huán)狀。（形式上，當(dāng)0 <= i < A.length 時(shí) C[i] = A[i]，且當(dāng) i >= 0 時(shí) C[i+A.length] = C[i]）

此外，子數(shù)組最多只能包含固定緩沖區(qū) A 中的每個(gè)元素一次。（形式上，對(duì)于子數(shù)組 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

示例 1：

輸入：[1,-2,3,-2]
輸出：3
解釋?zhuān)簭淖訑?shù)組 [3] 得到最大和 3

示例 2：

輸入：[5,-3,5]
輸出：10
解釋?zhuān)簭淖訑?shù)組 [5,5] 得到最大和 5 + 5 = 10

示例 3：

輸入：[3,-1,2,-1]
輸出：4
解釋?zhuān)簭淖訑?shù)組 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

示例 4：

輸入：[3,-2,2,-3]
輸出：3
解釋?zhuān)簭淖訑?shù)組 [3] 和 [3,-2,2] 都可以得到最大和 3

示例 5：

輸入：[-2,-3,-1]
輸出：-1
解釋?zhuān)簭淖訑?shù)組 [-1] 得到最大和 -1

提示：

-30000 <= A[i] <= 30000
1 <= A.length <= 30000
通過(guò)次數(shù)7,230提交次數(shù)21,014

解答

我們先來(lái)回顧一下非環(huán)形的情況，或者說(shuō)53題最大子序和的問(wèn)題。使用動(dòng)態(tài)規(guī)劃可以方便的解決。

【數(shù)組定義】定義數(shù)組dp，長(zhǎng)度與輸入數(shù)組nums一致，dp[i]表示以nums[i]結(jié)尾的子數(shù)組中和最大的連續(xù)子數(shù)組。

【初始情況】當(dāng)i=0時(shí)，子數(shù)組nums[:i+1]中只有一個(gè)元素，直接將nums[0]賦值給dp[0]即可。

【遞推公式】
對(duì)于i位置處的情況，有兩種可能性，一種是從dp[i-1]繼承過(guò)來(lái)，也就是nums[i]被添加到以nums[i-1]結(jié)尾的子數(shù)組中，將原先的子數(shù)組做了延長(zhǎng)；另一種情況就是原先的子數(shù)組到此位置，nums[i]成為新的子數(shù)組的開(kāi)頭。我們選取這兩種情況的子數(shù)組的最大值，填充在當(dāng)前位置i即可。

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

【最終返回值】

最終返回dp數(shù)組中的最大值即可。

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)]  # 記錄狀態(tài)：當(dāng)前以i結(jié)尾的最大值記錄在里面
        dp[0] = nums[0]

        for i in range(1, size):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])  # 記錄最大狀態(tài)
        return max(dp)

現(xiàn)在的情況是，原始數(shù)組首尾連接，形成環(huán)形，這樣一來(lái)，我們就需要考慮另外一種情況，也就是尾部一段連接開(kāi)頭一段的情況。我們從相反的角度來(lái)思考這種情況。假設(shè)數(shù)組被分成了ABC三段，能夠使得子數(shù)組的和最大的是C+A段，注意A段和C段在表達(dá)形勢(shì)上是斷開(kāi)的，但是在物理意義上是連續(xù)的，那么對(duì)于剩下的中間的B段，在形勢(shì)上就是連續(xù)的，而且這種狀況下，B段的和是最小的。如果我們能夠找到最小和的連續(xù)子數(shù)組，就從另一個(gè)角度確定了最大和的連續(xù)子數(shù)組（剩下的那兩部分就是），問(wèn)題就轉(zhuǎn)化為，如何找到非環(huán)形列表的最小和的連續(xù)子數(shù)組。很顯然，我們可以用與上述類(lèi)似的動(dòng)態(tài)規(guī)劃的方法來(lái)解決。

這里就不再使用數(shù)組了，因?yàn)槲覀冎魂P(guān)心當(dāng)前最新的最佳結(jié)果，因此可以降低一下空間復(fù)雜度，cur_min和res_min分別代表當(dāng)前子數(shù)組最小值，以及研究到現(xiàn)在為止的最佳結(jié)果。遍歷數(shù)組，對(duì)于當(dāng)前元素num，遞推公式為cur_min = min(num+cur_min, num)，并且用res_min及時(shí)記錄最新結(jié)果。當(dāng)我們找到了最小和的連續(xù)子數(shù)組，那么剩下的兩部分就組成了最大和的連續(xù)子數(shù)組，其和就是sum(A) - res_min。

綜上，根據(jù)最大和的連續(xù)子數(shù)組在形式上是連續(xù)的或者斷開(kāi)的，這兩種情況選其最優(yōu)即可。需要補(bǔ)充的是，這里需要判斷數(shù)組元素全部為負(fù)數(shù)的情況，這時(shí)直接返回最大值。

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

如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析