資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：查詢三個相同和的非重疊子列表的最大和
假設我們有一個名為nums的數字列表和另一個值k，我們需要找到給定列表中三個大小為k的非重疊子列表的最大和。
因此，如果輸入類似於nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k = 3，則輸出將為27，因為我們可以選擇子列表[2, 2, 2]、[4, 4, 4]和[3, 3, 3]，總和為27。
為了解決這個問題，我們將遵循以下步驟：
- P := [0]
- 對於A中的每個x，執行：
- 在P的末尾插入P[-1] + x
- Q := [P[i + K] - P[i] for i in range(0, len(P) - K)]
- prefix := Q[0:]
- suffix := Q[0:]
- 對於i in range(0, len(Q) -1)：
- prefix[i + 1] := max(prefix[i + 1], prefix[i])
- suffix[-(i + 1)] := max(suffix[-(i + 1)], suffix[-i])
- ret = [Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K - 1)]
- 返回ret中的最大值
示例（Python）
讓我們來看下面的實現以更好地理解：
class Solution: def solve(self, A, K): P = [0] for x in A: P.append(P[-1] + x) Q = [P[i + K] - P[i] for i in range(len(P) - K)] prefix = Q[:] suffix = Q[:] for i in range(len(Q) - 1): prefix[i + 1] = max(prefix[i + 1], prefix[i]) suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i]) return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K)) ob = Solution() nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k = 3 print(ob.solve(nums, k))
輸入
[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3
輸出
27
更新於：2020年12月12日
瀏覽量：106
廣告