Mảng phân vùng cho tổng tối đa trong Python

Giả sử chúng ta có một mảng số nguyên A, chúng ta phải phân chia mảng thành các mảng con (liền nhau) có độ dài tối đa là K. Sau khi phân vùng, mỗi mảng con có giá trị thay đổi để trở thành giá trị lớn nhất của mảng con đó. Chúng ta phải tìm tổng lớn nhất của mảng đã cho sau khi phân vùng. Vì vậy, nếu đầu vào là [1, 15, 7, 9, 2, 5, 10] và k =3, thì đầu ra sẽ là 84. Điều này là do mảng trở thành [15, 15, 15, 9, 10, 10 , 10]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một mảng có độ dài dp giống như A và điền vào giá trị này bằng 0
• cho tôi trong phạm vi từ 0 đến độ dài là A - 1
  • dp [i] =A [i] + dp [i - 1] nếu i - 1> =0 nếu không thì 0
  • tạm thời:=A [i]
  • cho j trong phạm vi từ 1 đến k - 1
    • nếu tôi - j> =0
      • index:=i - j
      • temp:=max of temp và A [i - j]
      • nếu chỉ mục - 1> =0, thì
        • dp [i]:=max of dp [i] and (temp * (i - index + 1) + dp [index - 1])
      • nếu không thì dp [i]:=max của dp [i] và 0
• trả về phần tử cuối cùng của dp

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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