পাইথনে ম্যাক্সিমাম সাবঅ্যারে (Maximum Subarray)

একটি ইন্টিজার অ্যারে দেওয়া থাকে। কমপক্ষে এক এলিমেন্ট বিশিষ্ট কন্টiguous সাবঅ্যারেটি খুঁজে বের করতে হবে যেন এর যোগফল সর্বোচ্চ হয়। কাডেনস অ্যালগরিদম (DP) ব্যবহার করা হয়েছে।

সমাধানের পদ্ধতি

1. dp অ্যারে তৈরি করুন (সাইজ len(nums))।
2. dp[0] = nums[0]।
3. for i in range(1, len(nums)): dp[i] = max(dp[i-1] + nums[i], nums[i])।
4. max(dp) রিটার্ন করুন।

উদাহরণ কোড

class Solution(object):
    def maxSubArray(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.maxSubArray(nums))

ইনপুট

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

আউটপুট

8