पायथन में समान राशि के 3 गैर-अतिव्यापी उप-सूचियों का सबसे बड़ा योग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है, हमें k आकार की दी गई सूची के तीन गैर-अतिव्यापी उप-सूचियों का सबसे बड़ा योग खोजना होगा।

इसलिए, यदि इनपुट संख्या =[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k =3 की तरह है, तो आउटपुट 27 होगा, जैसा कि हम चुन सकते हैं सबलिस्ट [2, 2, 2], [4, 4, 4], और [3, 3, 3], कुल योग 27 है।

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

• पी:=[0]
• ए में प्रत्येक एक्स के लिए, करें
  • पी के अंत में P[-1] + x डालें
• Q :=[P[i + K] - P[i] i के लिए 0 से लेकर P - K के आकार तक]
• उपसर्ग :=Q[सूचकांक 0 से अंत तक]
• प्रत्यय :=Q[सूचकांक 0 से अंत तक]
• मैं के लिए 0 से Q-1 के आकार के बीच में, करो
  • उपसर्ग[i + 1] :=अधिकतम उपसर्ग[i + 1], उपसर्ग[i]
  • प्रत्यय[~(i + 1)] :=अधिकतम प्रत्यय[~(i + 1)], प्रत्यय[~i]
• ret =(Q[i] + उपसर्ग[i - K] + प्रत्यय[i + K]) प्रत्येक i के लिए K से Q - K - 1 के आकार तक के लिए
• रिटर्न की अधिकतम वापसी

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class Solution:
   def solve(self, A, K):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      Q = [P[i + K] - P[i] for i in range(len(P) - K)]
      prefix = Q[:]
      suffix = Q[:]
      for i in range(len(Q) - 1):
         prefix[i + 1] = max(prefix[i + 1], prefix[i])
         suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])
      return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))
ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))

इनपुट

[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3

आउटपुट

27