পাইথনে সর্বাধিক যোগফল সহ সংলগ্ন সাবলিস্টের যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে আছে। আমাদেরকে সংলগ্ন সাবলিস্ট খুঁজে বের করতে হবে যার সর্বোচ্চ যোগফল আছে এবং এর যোগফলও ফেরত দিতে হবে। সুতরাং অ্যারে যদি 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]

• ডিপিতে সর্বোচ্চ রিটার্ন করুন

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

উদাহরণ

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