資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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 次檢視
廣告