Python程式：查詢兩個不相交子列表的最大和

假設我們有一個名為nums的數字列表和兩個值x和y，我們需要找到nums中兩個不相交子列表的最大和，這兩個子列表的長度分別為x和y。

例如，如果輸入為nums = [3, 2, 10, -2, 7, 6]，x = 3，y = 1，則輸出為22，因為我們選擇的長度為3的子列表為[3, 2, 10]，另一個子列表為[7]。

為了解決這個問題，我們將遵循以下步驟：

  • P := 一個包含單個元素0的列表
  • 對於A中的每個x，執行：
    • 將(P的最後一個元素 + x)插入到P的末尾
  • 定義一個函式solve()。它將接收len1, len2作為引數
  • Q := 一個列表，其元素為(P[i + len1] - P[i])，其中i的範圍是從0到P的大小 - len1
  • prefix := Q的一個副本
  • 對於從0到prefix大小 - 1的每個i，執行：
    • prefix[i + 1] := prefix[i + 1]和prefix[i]中的最大值
  • ans := -infinity
  • 對於從len1到P的大小 - len2的每個i，執行：
    • left := prefix[i - len1]
    • right := P[i + len2] - P[i]
    • ans := ans和(left + right)中的最大值
  • 返回ans
  • 在主方法中執行以下操作：
  • 返回solve(len1, len2)和solve(len2, len1)中的最大值

讓我們看看下面的實現來更好地理解：

示例

 線上演示

class Solution:
   def solve(self, A, len1, len2):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      def solve(len1, len2):
         Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
         prefix = Q[:]
         for i in range(len(prefix) - 1):
            prefix[i + 1] = max(prefix[i + 1], prefix[i])
            ans = float("-inf")
            for i in range(len1, len(P) - len2):
               left = prefix[i - len1]
               right = P[i + len2] - P[i]
            ans = max(ans, left + right)
            return ans
         return max(solve(len1, len2), solve(len2, len1))
ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

輸入

[3, 2, 10, -2, 7, 6], 3, 1

輸出

22

更新於：2020年11月20日

246 次檢視

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告