สมมติว่าเรามีรายการตัวเลขที่เรียกว่า 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]
- สำหรับแต่ละ x ใน A ทำ
- ใส่ P[-1] + x ที่ส่วนท้ายของ P
- Q :=[P[i + K] - P[i] for i ในช่วง 0 ถึงขนาด P - K]
- คำนำหน้า :=Q[จากดัชนี 0 ถึงจุดสิ้นสุด]
- คำต่อท้าย :=Q[จากดัชนี 0 ถึงจุดสิ้นสุด]
- สำหรับ i ในช่วง 0 ถึงขนาด Q - 1 ทำ
- คำนำหน้า[i + 1] :=สูงสุดของคำนำหน้า[i + 1] คำนำหน้า[i]
- ส่วนต่อท้าย[~(i + 1) ] :=สูงสุดของคำต่อท้าย[~(i + 1) ], คำต่อท้าย[~i]
- ret =(Q[i] + prefix[i - K] + suffix[i + K]) สำหรับแต่ละ i ในช่วง K ถึงขนาดของ 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
