पायथन में सबसे बड़े K सबलिस्ट का योग खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, और एक मान k, जो nums को k बार जोड़कर बनी एक बड़ी सूची को दर्शाता है। हमें सबसे बड़े योग वाले सन्निहित सबलिस्ट का योग ढूंढना है।

उदाहरण के लिए, यदि इनपुट nums = [1, 3, 4, -5] और k = 1 है, तो आउटपुट 11 होगा, क्योंकि हम सबलिस्ट [2, 4, 5] ले सकते हैं। (नोट: उदाहरण में इनपुट/आउटपुट में विसंगति है, कोड देखें)।

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

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

• s := ans := lo := 0
• min(k, 2) बार दोहराएं:
  • प्रत्येक x के लिए nums में:
    • s += x
    • lo = min(lo, s)
    • ans = max(ans, s - lo)
• ans + max(0, sum(nums)) * max(0, k-2) लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, nums, k):
        s = ans = lo = 0
        for _ in range(min(k, 2)):
            for x in nums:
                s += x
                lo = min(lo, s)
                ans = max(ans, s - lo)
        return ans + max(0, sum(nums)) * max(0, k-2)

ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

इनपुट

[2, 4, 5, -4], 1

आउटपुट

11