Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में दो नॉन-ओवरलैपिंग सबलिस्ट्स का अधिकतम योग खोजने का प्रोग्राम


मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और दो मान x और y हैं, हमें nums में दो नॉन-ओवरलैपिंग सबलिस्ट्स का अधिकतम योग ढूंढना है जिनकी लंबाई क्रमशः x और y है।

उदाहरण के लिए, यदि इनपुट nums = [3, 2, 10, -2, 7, 6], x = 3, y = 1 है, तो आउटपुट 22 होगा, क्योंकि लंबाई 3 के लिए हम [3, 2, 10] चुनते हैं और लंबाई 1 के लिए [7]।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • P := [0] से शुरू करें
  • प्रत्येक x के लिए A में: P.append(P[-1] + x) (प्रीफिक्स सम)
  • एक फंक्शन solve(len1, len2) परिभाषित करें:
    • Q := [P[i+len1] - P[i] for i in range(len(P)-len1)]
    • prefix := Q की कॉपी
    • i के लिए 0 से len(prefix)-1: prefix[i+1] = max(prefix[i+1], prefix[i])
    • ans := -infinity
    • i के लिए len1 से len(P)-len2 तक:
      • left := prefix[i-len1]
      • right := P[i+len2] - P[i]
      • ans := max(ans, left+right)
    • ans लौटाएं
  • मुख्य मेथड से: max(solve(len1, len2), solve(len2, len1)) लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, A, len1, len2):
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        def solve(len1, len2):
            Q = [P[i+len1] - P[i] for i in range(len(P)-len1)]
            prefix = Q[:]
            for i in range(len(prefix)-1):
                prefix[i+1] = max(prefix[i+1], prefix[i])
            ans = float("-inf")
            for i in range(len1, len(P)-len2):
                left = prefix[i-len1]
                right = P[i+len2] - P[i]
                ans = max(ans, left+right)
            return ans
        return max(solve(len1, len2), solve(len2, len1))

ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

इनपुट

[3, 2, 10, -2, 7, 6], 3, 1

आउटपुट

22

  1. पायथन में ट्री के गैर-आसन्न नोड्स के अधिकतम योग को खोजने का प्रोग्राम पायथन में ट्री के गैर-आसन्न नोड्स के अधिकतम योग को खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें उन मानों का अधिकतम योग ढूंढना है जो इस शर्त पर प्राप्त किया जा सकता है कि कोई दो मान आसन्न पैरेंट-टू-चाइल्ड न हों।इसलिए, यदि इनपुट इस तरह हैतो आउटपुट 17 होगा क्योंकि 10, 4, 3 एक-दूसरे से आसन्न नहीं हैं।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

  1. - पायथन में सभी सन्निकट सबलिस्ट के योग का योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, अब हर सन्निकट सबअरे पर विचार करें। इनमें से प्रत्येक सबअरे का योग करें और इन सभी मानों का योग लौटाएं। अंत में, परिणाम को 10**9 + 7 से मोड करें। उदाहरण के लिए, यदि इनपुट है nums = [3, 4, 6], तो आउटपुट होगा 43, क्योंकि हमारे पास निम्नलिखित सबअरे ह

  1. - Python प्रोग्राम से जांचें कि कोई संख्या दो की घात है या नहीं

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक संख्या दी गई है, हमें जांचने की आवश्यकता है कि संख्या दो की घात है या नहीं। हम इसे नीचे चर्चा किए गए दो दृष्टिकोणों का उपयोग करके हल कर सकते हैं। दृष्टिकोण 1: दिए गए संख्या का बेस 2 पर लॉग लेकर घात प्राप्त क