पायथन में अधिकतम योग के साथ सन्निहित सबलिस्ट का योग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी ए है। हमें उस सन्निहित उपन्यास को खोजना है जिसमें अधिकतम योग है, और उसका योग भी वापस करना है। तो अगर सरणी ए ए =[-2,1,-3,4,-1,2,1,-5,4] की तरह है, तो योग 6 होगा। और सबरेरे [4, -1, 2, 1].

इसे हल करने के लिए हम गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करने का प्रयास करेंगे।

• एक सरणी dp को A के आकार के समान परिभाषित करें, और इसे 0 से भरें

• डीपी [0] :=ए[0]

• i के लिए :=1 से A – 1 के आकार तक

  • dp[i] :=अधिकतम dp[i – 1] + A[i] और A[i]

• डीपी में अधिकतम वापसी

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

उदाहरण

class Solution(object):
   def solve(self, nums):
      dp = [0 for i in range(len(nums))]
      dp[0] = nums[0]
      for i in range(1,len(nums)):
         dp[i] = max(dp[i-1]+nums[i],nums[i])
      return max(dp)
nums = [-2,1,-3,7,-2,2,1,-5,4]
ob1 = Solution()
print(ob1.solve(nums))

इनपुट

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

आउटपुट

8