สมมติว่าเรามีอาร์เรย์จำนวนเต็ม A เราต้องแบ่งอาร์เรย์เป็นอาร์เรย์ย่อย (ต่อเนื่องกัน) ที่มีความยาวมากที่สุด K หลังจากการแบ่งพาร์ติชัน แต่ละอาร์เรย์ย่อยจะมีการเปลี่ยนแปลงค่าเพื่อให้กลายเป็นค่าสูงสุดของอาร์เรย์ย่อยนั้น เราต้องหาผลรวมที่ใหญ่ที่สุดของอาร์เรย์ที่กำหนดหลังจากแบ่งพาร์ติชั่น ดังนั้นหากอินพุตเป็น [1, 15, 7, 9, 2, 5, 10] และ k =3 ผลลัพธ์จะเป็น 84 เนื่องจากอาร์เรย์กลายเป็น [15, 15, 15, 9, 10, 10 , 10]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างอาร์เรย์ dp หนึ่งอันที่มีความยาวเท่ากับ A และเติมค่านี้ด้วย 0
- สำหรับ i ในช่วง 0 ถึงความยาวของ A - 1
- dp[i] =A[i] + dp[i - 1] ถ้า i – 1>=0 มิฉะนั้น 0
- อุณหภูมิ :=A[i]
- สำหรับ j ในช่วง 1 ถึง k – 1
- ถ้า i – j>=0
- ดัชนี :=ผม – เจ
- อุณหภูมิ :=สูงสุดของอุณหภูมิและ A[i - j]
- ถ้าดัชนี – 1>=0 แล้ว
- dp[i] :=สูงสุดของ dp[i] และ (temp*(i – index + 1) + dp[index - 1])
- มิฉะนั้น dp[i] :=สูงสุดของ dp[i] และ 0
- ถ้า i – j>=0
- คืนค่าองค์ประกอบสุดท้ายของ dp
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def maxSumAfterPartitioning(self, A, K): dp = [0 for i in range(len(A))] for i in range(len(A)): dp[i] = A[i] + (dp[i-1] if i-1>=0 else 0) temp = A[i] for j in range(1,K): if i-j>=0: index = i-j temp = max(temp,A[i-j]) dp[i] = max(dp[i],temp*(i-index+1) + (dp[index-1] if index-1 >=0 else 0)) return dp[-1] ob = Solution() print(ob.maxSumAfterPartitioning([1,15,7,9,2,5,10],3))
อินพุต
[1,15,7,9,2,5,10] 3
ผลลัพธ์
84
