โจทย์: กำหนดอาร์เรย์ A แบ่งเป็น subarrays ต่อเนื่องยาวสูงสุด K แต่ละ subarray จะเปลี่ยนค่าทุกตัวเป็นค่าสูงสุดใน subarray นั้น หาผลรวมสูงสุดหลังแบ่ง
ตัวอย่าง
Input: A = [1, 15, 7, 9, 2, 5, 10], K = 3
Output: 84 (แบ่งเป็น [1,15,7] [9] [2,5,10] → [15,15,15] [9] [10,10,10] = 84)
อัลกอริทึม: Dynamic Programming
dp[i] = ผลรวมสูงสุดสำหรับ prefix A[0..i]
Transition: ลองทุกความยาว subarray ที่จบที่ i (1 ถึง K)
ตัวอย่างโค้ด Python
class Solution(object):
def maxSumAfterPartitioning(self, A, K):
n = len(A)
dp = [0] * n
for i in range(n):
# กรณี subarray ยาว 1
dp[i] = A[i] + (dp[i-1] if i > 0 else 0)
max_val = A[i]
# ลอง subarray ยาว 2 ถึง K
for j in range(1, K):
if i - j >= 0:
max_val = max(max_val, A[i - j])
# ค่า subarray = max_val * length + dp[before_subarray]
prev = dp[i - j - 1] if i - j - 1 >= 0 else 0
dp[i] = max(dp[i], max_val * (j + 1) + prev)
return dp[-1]
# ทดสอบ
ob = Solution()
print(ob.maxSumAfterPartitioning([1,15,7,9,2,5,10], 3)) # Output: 84
ตัวอย่าง Input/Output
Input: [1,15,7,9,2,5,10] 3 Output: 84
ความซับซ้อน: Time O(n×K), Space O(n)
