পাইথনে একটি উপাদান সরিয়ে কনটিগুয়াস স্ট্রিক্টলি ইনক্রিজিং সাবলিস্টের সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

মনে করুন nums একটি সংখ্যার তালিকা। একটি বা শূন্য উপাদান সরিয়ে কনটিগুয়াস স্ট্রিক্টলি ইনক্রিজিং সাবলিস্টের সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করতে হবে।

উদাহরণস্বরূপ, nums = [30, 11, 12, 13, 14, 15, 18, 17, 32] হলে আউটপুট ৭, কারণ ১৮ সরিয়ে [11,12,13,14,15,17,32] পাওয়া যায়।

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

n := nums-এর আকার
pre := n আকারের তালিকা, ১ দিয়ে পূরিত
i = 1 থেকে n-1 পর্যন্ত, যদি nums[i] > nums[i-1], pre[i] = pre[i-1]+1
suff := n আকারের তালিকা, ১ দিয়ে পূরিত
i = n-2 থেকে 0 পর্যন্ত, যদি nums[i] < nums[i+1], suff[i] = suff[i+1]+1
ans := max(max(pre), max(suff))
i = 1 থেকে n-2 পর্যন্ত, যদি nums[i-1] < nums[i+1], ans = max(ans, pre[i-1]+suff[i+1])
ans ফেরত দিন

উদাহরণ

class Solution:
    def solve(self, nums):
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                pre[i] = pre[i - 1] + 1
        suff = [1] * n
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                suff[i] = suff[i + 1] + 1
        ans = max(max(pre), max(suff))
        for i in range(1, n - 1):
            if nums[i - 1] < nums[i + 1]:
                ans = max(ans, pre[i - 1] + suff[i + 1])
        return ans

ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))

ইনপুট

[30, 11, 12, 13, 14, 15, 18, 17, 32]