পাইথনে কাস্টমার মুড বদলিয়ে সর্বোচ্চ হ্যাপি কাস্টমার বের করা

প্রতিটি মিনিটে customers[i] কাস্টমার আসে। mood[i]=1 মানে হ্যাপি, 0 মানে স্যাড। একটি সাবঅ্যারে সাইজ k এর মূড ১ করে দিলে সর্বোচ্চ কতজন হ্যাপি করা যায়।

ইনপুট উদাহরণ

customers = [2, 3, 6, 6, 3]
mood = [1, 1, 0, 0, 0]
k = 2

আউটপুট: 17 (ইনডেক্স ২,৩-কে ১ করলে: 2+3+6+6=17)

অ্যালগরিদম

1. প্রিফিক্স সাম অ্যারে a বানান যেখানে a[i+1] = ইনডেক্স i পর্যন্ত স্যাড কাস্টমার সমষ্টি।
2. স্লাইডিং উইন্ডো সাইজ k দিয়ে ম্যাক্সিমাম এক্সট্রা হ্যাপি কাস্টমার বের করুন (a[i] - a[i-k])।
3. বেস হ্যাপি কাস্টমার + ম্যাক্স এক্সট্রা = আন্স।

পাইথন কোড

def solve(customers, mood, k):
    n = len(mood)
    a = [0] * (n + 1)
    s = 0
    for i in range(n):
        a[i+1] = a[i]
        if mood[i]:
            s += customers[i]
        else:
            a[i+1] += customers[i]
    d = 0
    for i in range(k, n+1):
        d = max(d, a[i] - a[i-k])
    return s + d

# টেস্ট
print(solve([2,3,6,6,3], [1,1,0,0,0], 2))  # 17

ব্যাখ্যা

প্রিফিক্স সাম + স্লাইডিং উইন্ডো। সময় জটিলতা O(n), স্পেস O(n)।