পাইথনে সর্বোচ্চ সাবারে

ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে A আছে। আমাদেরকে সংলগ্ন সাবয়ারে খুঁজে বের করতে হবে যার দৈর্ঘ্য কমপক্ষে একটি হবে, এবং যেটির যোগফল সবচেয়ে বেশি এবং এর যোগফলও ফেরত দিতে হবে। সুতরাং অ্যারে যদি A =[-2,1,-3,4,-1,2,1,-5,4] এর মতো হয়, তাহলে যোগফল হবে 6। এবং সাবয়ারে হবে [4, -1 , 2, 1]

এটি সমাধান করার জন্য আমরা ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করার চেষ্টা করব।

• A এর আকারের মতো একটি অ্যারে ডিপি সংজ্ঞায়িত করুন এবং এটি 0 দিয়ে পূরণ করুন
• dp[0] :=A[0]
• এর জন্য i =1 থেকে A – 1
  এর আকার
  • dp[i] :=সর্বাধিক dp[i – 1] + A[i] এবং A[i]
• ডিপিতে সর্বোচ্চ রিটার্ন

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

উদাহরণ (পাইথন)

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