পাইথনে Maximum Product Subarray (সর্বাধিক গুণফলযুক্ত সাবঅ্যারে)

মান করুন nums নামক একটি ইন্টিজার অ্যারে আছে। আমাদের সেই অ্যারেতে একটি সन्नিহিত সাবঅ্যারে বের করতে হবে (কমপক্ষে একটি সংখ্যা থাকবে) যেটির গুণফল সর্বাধিক। অ্যারে [2,3,-2,4] হলে আউটপুট হবে ৬, কারণ সন্নিহিত সাবঅ্যারে [2,3]-র গুণফল সর্বাধিক।

সমাধানের ধাপগুলো (ডাইনামিক প্রোগ্রামিং):

max_list := nums-এর সাইজের লিস্ট, ০ দিয়ে ফিল করা
min_list := nums-এর সাইজের লিস্ট, ০ দিয়ে ফিল করা
max_list[0] := nums[0] এবং min_list[0] := nums[0]
i ১ থেকে len(nums) পর্যন্ত
- max_list[i] = max(max_list[i-1]*nums[i], min_list[i-1]*nums[i], nums[i])
- min_list[i] = min(min_list[i-1]*nums[i], nums[i], max_list[i-1]*nums[i])
max_list-এর সর্বাধিক মান রিটার্ন করুন

নিচে ইমপ্লিমেন্টেশন দেওয়া হলো:

উদাহরণ

class Solution(object):
    def maxProduct(self, nums):
        max_list = [0] * len(nums)
        min_list = [0] * len(nums)
        max_list[0] = nums[0]
        min_list[0] = nums[0]
        for i in range(1, len(nums)):
            max_list[i] = max(max(max_list[i-1]*nums[i], min_list[i-1]*nums[i]), nums[i])
            min_list[i] = min(min(min_list[i-1]*nums[i], nums[i]), max_list[i-1]*nums[i])
        return max(max_list)

ob1 = Solution()
print(ob1.maxProduct([2, 3, -2, 4, -5, -6, 2]))

ইনপুট

[2,3,-2,4,-5,-6,2]