पायथन में अधिकतम उपसरणी

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

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

• A के समान आकार की एक सरणी dp परिभाषित करें, और इसे 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])
        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