[leetcode筆記] 1031. 兩個非重疊子數組的最大和

• • 題目描述
  • • • 示例 1：
      • 示例 2：
      • 示例 3：
      • 提示：
  • 解題思路
  • • • 代碼

題目描述

給出非負整數數組 A ，傳回兩個非重疊（連續）子數組中元素的最大和，子數組的長度分别為 L 和 M。（這裡需要澄清的是，長為 L 的子數組可以出現在長為 M 的子數組之前或之後。）

從形式上看，傳回最大的 V，而 V = (A[i] + A[i+1] + … + A[i+L-1]) + (A[j] + A[j+1] + … + A[j+M-1]) 并滿足下列條件之一：

0 <= i < i + L - 1 < j < j + M - 1 < A.length

, 或

0 <= j < j + M - 1 < i < i + L - 1 < A.length.

示例 1：

輸入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2

輸出：20

解釋：子數組的一種選擇中，[9] 長度為 1，[6,5] 長度為 2。

示例 2：

輸入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2

輸出：29

解釋：子數組的一種選擇中，[3,8,1] 長度為 3，[8,9] 長度為 2。

示例 3：

輸入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3

輸出：31

解釋：子數組的一種選擇中，[5,6,0,9] 長度為 4，[0,3,8] 長度為 3。

提示：

L >= 1

M >= 1

L + M <= A.length <= 1000

0 <= A[i] <= 1000

解題思路

• 題目要求兩個子數組不能重疊
• 此題兩個子數組不能單獨尋找，不能先找一個最大的子數組，再找另一個最大子數組，須同時進行。
• 用雙重循環周遊：先拿出一個連續子數組，再從剩餘的中拿出另一個連續子數組，将兩個數組相加，如此循環，再與下一對子數組對比，取最大值。
• 有一點值得

  注意

  ：外層循環次數比内層循環次數少，能夠減少運作時間，是以，需要對兩個子數組的長度進行判斷。

代碼

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        Max = 0
        if L<M:
            L, M = M, L
        # L大，則外循環次數少
        for i in range(len(A)-L+1):
            s1 = sum(A[i:i+L])
            for j in range(i-M+1):
                s2 = sum(A[j:j+M])
                Max = max(Max, s1+s2)
            for j in range(i+L, len(A)-M+1):
                s2 = sum(A[j:j+M])
                Max = max(Max, s1+s2)
        return Max