C++-এ ক্যান্ডি (Candy) সমস্যা

ক্যান্ডি সমস্যা

N শিশু লাইনে দাঁড়িয়ে আছে। প্রতিটির একটি রেটিং আছে। ক্যান্ডি বিতরণ করতে হবে এমনকি:

1. প্রতিটি শিশু কমপক্ষে ১টি ক্যান্ডি পাবে
2. যে শিশুর রেটিং বেশি, সে তার প্রতিবেশীদের চেয়ে বেশি ক্যান্ডি পাবে

ন্যূনতম মোট কতটি ক্যান্ডি দরকার?

উদাহরণ: [1,1,3] → ক্যান্ডি: [1,1,2] → মোট: ৪

সমাধানের পদ্ধতি (দুই পাস DP / Greedy)

• সকলকে ১টি কாண்டি দিয়ে শুরু করুন (dp[i] = 1)
• বাম থেকে ডান পাস: যদি rating[i] > rating[i-1] হয়, তবে dp[i] = dp[i-1] + 1
• ডান থেকে বাম পাস: যদি rating[i] > rating[i+1] হয়, তবে dp[i] = max(dp[i], dp[i+1] + 1)
• মোট ক্যান্ডি = sum(dp)

সময় জটিলতা: O(n), স্পেস: O(n)

C++ কোড উদাহরণ

[1,1,3]

আউটপুট

4