ধরুন N শিশু আছে, তারা একটি লাইনে দাঁড়িয়ে আছে। এখানে প্রতিটি শিশুকে একটি রেটিং মান বরাদ্দ করা হয়। আমরা নিম্নলিখিত প্রয়োজনীয়তা সাপেক্ষে এই শিশুদের ক্যান্ডি সরবরাহ করছি -
-
প্রতিটি শিশুর অন্তত একটি ক্যান্ডি থাকতে হবে।
-
যেসব শিশুর রেটিং বেশি তাদের প্রতিবেশীদের চেয়ে বেশি ক্যান্ডি পাবে।
আমাদের অবশ্যই ন্যূনতম সংখ্যক ক্যান্ডি খুঁজে বের করতে হবে?
সুতরাং ইনপুট যদি [1,1,3] এর মত হয়, তাহলে আউটপুট হবে 4। তাই তারা যথাক্রমে 1, 1 এবং 2 ক্যান্ডি পাবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=অ্যারের রেটিংয়ের আকার, n আকারের dp নামে অ্যারে তৈরি করুন, 1 ব্যবহার করে এটি পূরণ করুন
-
ret :=0
-
1 থেকে n – 1
রেঞ্জের জন্য i-
যদি রেটিং[i]> রেটিং[i – 1] হয়, তাহলে dp[i] :=dp[i - 1] + 1
-
-
n - 2 থেকে 0
রেঞ্জে i এর জন্য-
যদি রেটিং[i]> রেটিং[i + 1] হয়, তাহলে dp[i] :=dp[i] এবং dp[i + 1] + 1
এর সর্বোচ্চ
-
-
ret :=dp এর উপাদানগুলির যোগফল
-
রিটার্ন রিটার্ন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector <int> dp(n, 1);
int ret = 0;
for(int i = 1; i < n; i++){
if(ratings[i] > ratings[i - 1]){
dp[i] = dp[i - 1] + 1;
}
}
for(int i = n - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1]){
dp[i] = max(dp[i], dp[i + 1] + 1);
}
}
for(int i = 0; i < n; i+=1){
ret += dp[i];
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,1,3};
cout << (ob.candy(v));
} ইনপুট
[1,1,3]
আউটপুট
4
