কাডেনের অ্যালগরিদম দিয়ে ম্যাক্সিমাম সাবঅ্যারে সমস্যা সমাধানের পাইথন প্রোগ্রাম

কাডেনের অ্যালগরিদম (Kadane's Algorithm) ব্যবহার করে O(n) টাইমে ম্যাক্সিমাম সাবঅ্যারে সাম বের করা হয়।

উদাহরণ

def max_subarray(arr):
    max_ending_here = max_so_far = arr[0]
    start = end = temp_start = 0
    
    for i in range(1, len(arr)):
        if max_ending_here + arr[i] > arr[i]:
            max_ending_here += arr[i]
        else:
            max_ending_here = arr[i]
            temp_start = i
        
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i
    
    return start, end, max_so_far

nums = list(map(int, input("সংখ্যাগুলো দিন: ").split()))
s, e, max_sum = max_subarray(nums)
print(f"ম্যাক্স সাবঅ্যারে: ইনডেক্স {s} থেকে {e}, সাম = {max_sum}")

আউটপুট

সংখ্যাগুলো দিন: 2 5 7 12 6 8
ম্যাক্স সাবঅ্যারে: ইনডেক্স 0 থেকে 5, সাম = 40

ব্যাখ্যা

• max_ending_here: করেন্ট সাবঅ্যারে সাম (এই ইনডেক্সে শেষ)।

• max_so_far: সবচেয়ে বড় সাবঅ্যারে সাম (এখন পর্যন্ত)।

• নেগেটিভ হলে নতুন সাবঅ্যারে শুরু (temp_start আপডেট)।

• স্টার্ট/এন্ড ইনডেক্স ট্র্যাক করে সাবঅ্যারে লোকেশন জানা যায়।

• টাইম কমপ্লেক্সিটি O(n), স্পেস O(1)۔