पायथन में अधिकतम सबरे

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

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

• एक सरणी dp को A के आकार के समान परिभाषित करें, और इसे 0 से भरें
• dp[0] :=A[0]
• i =1 के लिए A - 1 के आकार के लिए
  • dp[i] :=अधिकतम dp[i – 1] + A[i] और A[i]
• dp में अधिकतम वापसी

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

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

class Solution(object):
   def maxSubArray(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      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])
      #print(dp)
      return max(dp)
nums = [-2,1,-3,7,-2,2,1,-5,4]
ob1 = Solution()
print(ob1.maxSubArray(nums))

इनपुट

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

आउटपुट

8