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

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

উদাহরণ: nums = [35, 5, 6, 7, 8, 9, 12, 11, 26] হলে আউটপুট 7। কারণ 12 সরিয়ে দিলে [5, 6, 7, 8, 9, 11, 26] হয় যা দৈর্ঘ্য ৭।

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

দুটি অ্যারে ব্যবহার করে প্রিফিক্স এবং সাফিক্স দৈর্ঘ্য প্রিক্যালকুলেট করুন:

• end[i]: ইনডেক্স i তে শেষ হওয়া ইনক্রিজিং সাবলিস্টের দৈর্ঘ্য।
• start[i]: ইনডেক্স i থেকে শুরু হওয়া ইনক্রিজিং সাবলিস্টের দৈর্ঘ্য।

তারপর প্রতিটি ইনডেক্স k সরিয়ে দেখুন যে nums[k-1] < nums[k+1] কিনা। হ্যাঁ হলে end[k-1] + start[k+1] দৈর্ঘ্য সম্ভব।

পাইথন কোড

def solve(nums):
    if not nums:
        return 0
    
    n = len(nums)
    end = [1] * n    # প্রিফিক্স দৈর্ঘ্য
    start = [1] * n  # সাফিক্স দৈর্ঘ্য
    
    # বাম থেকে ডান: end[i] ক্যালকুলেট করুন
    for i in range(1, n):
        if nums[i] > nums[i-1]:
            end[i] = end[i-1] + 1
    
    # ডান থেকে বাম: start[i] ক্যালকুলেট করুন
    for j in range(n-2, -1, -1):
        if nums[j+1] > nums[j]:
            start[j] = start[j+1] + 1
    
    # কোনো উপাদান সরানো ছাড়া সর্বোচ্চ দৈর্ঘ্য
    res = max(max(end), max(start))
    
    # প্রতিটি মধ্যম উপাদান সরিয়ে চেক করুন
    for k in range(1, n-1):
        if nums[k-1] < nums[k+1]:
            res = max(res, end[k-1] + start[k+1])
    
    return res

# টেস্ট
nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
print(solve(nums))  # আউটপুট: 7

সময় জটিলতা

O(n) - তিনটি লিনিয়ার পাস। স্পেস O(n)।