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

मान लीजिए कि हमारे पास एक पूर्णांक सरणी ए है, हमें सरणी को अधिकतम के (सन्निहित) लंबाई के उप-सरणी में विभाजित करना होगा। विभाजन के बाद, प्रत्येक उप-सरणी का मान उस उप-सरणी का अधिकतम मान बनने के लिए बदल जाता है। हमें विभाजन के बाद दिए गए सरणी का सबसे बड़ा योग ज्ञात करना है। तो अगर इनपुट [1, 15, 7, 9, 2, 5, 10] और के =3 जैसा है, तो आउटपुट 84 होगा। ऐसा इसलिए है क्योंकि सरणी [15, 15, 15, 9, 10, 10] बन जाती है। , 10]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक सरणी dp लंबाई A के समान बनाएं, और इसे 0 से भरें
मैं के लिए 0 से ए की लंबाई तक - 1
- dp[i] =A[i] + dp[i - 1] अगर i – 1>=0 अन्यथा 0
- अस्थायी:=ए[i]
- जे के लिए 1 से के - 1 की सीमा में
  - अगर मैं - जे>=0
    - सूचकांक :=i – j
    - अस्थायी:=अधिकतम तापमान और A[i - j]
    - यदि अनुक्रमणिका – 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