पायथन में अधिकतम योग के लिए सरणी विभाजन

मान लीजिए हमारे पास एक पूर्णांक सरणी 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
- temp := A[i]
- j के लिए 1 से k - 1 तक की रेंज में
  - यदि i - j >= 0
    - index := i - j
    - temp := temp और A[i - j] का अधिकतम
    - यदि index - 1 >= 0, तो
      - dp[i] := dp[i] और (temp*(i - index + 1) + dp[index - 1]) का अधिकतम
    - अन्यथा dp[i] := dp[i] और 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