Phân chia mảng để có tổng lớn nhất trong Python

Cho mảng nguyên A, phân chia thành các mảng con liên tiếp độ dài tối đa K. Sau phân chia, mỗi mảng con được thay thế bằng giá trị max của nó. Tìm tổng lớn nhất có thể đạt được.

Ví dụ: A = [1,15,7,9,2,5,10], K=3 -> phân chia [1,15,7], [9], [2,5,10] -> max lần lượt 15,9,10 -> mảng trở thành [15,15,15,9,10,10,10] tổng = 84.

Giải thuật quy hoạch động

• Tạo mảng dp độ dài n, khởi tạo 0.
• Duyệt i từ 0 đến n-1:
  • dp[i] = A[i] + (dp[i-1] nếu i>0 else 0) – trường hợp không gộp.
  • temp = A[i].
  • Duyệt j từ 1 đến K-1 (kích thước nhóm):
  • Nếu i-j >= 0: index = i-j, temp = max(temp, A[i-j]).
  • dp[i] = max(dp[i], temp * (i-index+1) + (dp[index-1] nếu index>0 else 0)).
• Trả về dp[-1].

Ví dụ

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))

Đầu vào

[1,15,7,9,2,5,10] 3

Đầu ra

84