পাইথনে সর্বোচ্চ সমষ্টিয়ুক্ত সন্নিবিষ্ট সাবলিস্টের সমষ্টি খুঁজে বের করার প্রোগ্রাম

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

সমাধানের ধাপসমূহ (ডাইনামিক প্রোগ্রামিং)

• dp অ্যারে A-এর আকারের তৈরি করুন, 0 দিয়ে ভরুন।
• dp[0] := A[0]
• i = 1 থেকে A-এর আকার-১ পর্যন্ত: dp[i] := max(dp[i-1] + A[i], A[i])
• dp-র সর্বোচ্চ মান ফেরত দিন।

উদাহরণ কোড

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