สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และค่า x และ y สองค่า เราต้องหาผลรวมสูงสุดของรายการย่อยที่ไม่ทับซ้อนกันสองรายการในหน่วย num ซึ่งมีความยาว x และ y
ดังนั้นหากอินพุตเป็น nums =[3, 2, 10, -2, 7, 6] x =3 y =1 ผลลัพธ์จะเป็น 22 เนื่องจากรายการย่อยที่มีความยาว 3 เราเลือก [3, 2, 10] และอีกอันเราเลือก [7].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- P :=รายการที่มีองค์ประกอบเดียว 0
- สำหรับแต่ละ x ใน A ทำ
- แทรก (องค์ประกอบสุดท้ายของ P + x) ที่ส่วนท้ายของ P
- กำหนดฟังก์ชัน Solve() นี่จะใช้เวลา len1, len2
- Q :=รายการที่มีองค์ประกอบ (P[i + len1] - P[i]) สำหรับแต่ละ i ในช่วง 0 ถึงขนาดของ P - len1
- คำนำหน้า :=สำเนาของ Q
- สำหรับ i ในช่วง 0 ถึงขนาดของคำนำหน้า - 1 ทำ
- คำนำหน้า[i + 1] :=สูงสุดของคำนำหน้า[i + 1] และคำนำหน้า[i]
- ตอบ :=-อินฟินิตี้
- สำหรับฉันในช่วง len1 ถึงขนาด P - len2 ทำ
- left :=prefix[i - len1]
- ขวา :=P[i + len2] - P[i]
- ans :=สูงสุดของ ans และ (ซ้าย + ขวา)
- คืนสินค้า
- จากวิธีหลัก ให้ทำดังนี้ -
- คืนค่าสูงสุดของ Solve(len1, len2) , dissolve(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
