পাইথনে তালিকা থেকে অ-সন্নিহিত উপাদানগুলোর সর্বোচ্চ সমষ্টি খুঁজে বের করার প্রোগ্রাম

ধরা যাক nums নামক একটি সংখ্যার তালিকা আছে, আমাদের অ-সন্নিহিত (non-adjacent) সংখ্যাগুলোর সর্বোচ্চ সমষ্টি বের করতে হবে। সংখ্যাগুলো ০ বা নেতিবাচকও হতে পারে।

উদাহরণ: [3, 5, 7, 3, 6] হলে আউটপুট 16, কারণ 3, 7, 6 নিলে 16 হয়।

সমাধানের ধাপসমূহ

• যদি nums-এর আকার <= 2 হয়, max(nums) ফেরত দিন।
• noTake := 0, take := nums[0]
• i = 1 থেকে nums-এর আকার পর্যন্ত:
• take := noTake + nums[i]
• noTake := max(noTake, take)
• max(noTake, take) ফেরত দিন।

উদাহরণ কোড

class Solution:
    def solve(self, nums):
        if len(nums) <= 2:
            return max(nums)
        noTake = 0
        take = nums[0]
        for i in range(1, len(nums)):
            take, noTake = noTake + nums[i], max(noTake, take)
        return max(noTake, take)

ob = Solution()
nums = [3, 5, 7, 3, 6]
print(ob.solve(nums))

ইনপুট

[3, 5, 7, 3, 6]

আউটপুট

16