मान लीजिए N बच्चे हैं, वे एक लाइन में खड़े हैं। यहां प्रत्येक बच्चे को एक रेटिंग मान दिया गया है। हम इन बच्चों को कैंडी की आपूर्ति निम्नलिखित आवश्यकताओं के अधीन कर रहे हैं -
प्रत्येक बच्चे के पास कम से कम एक कैंडी होनी चाहिए।
जिन बच्चों की रेटिंग अधिक है, उन्हें अपने पड़ोसियों से अधिक कैंडी मिलेगी।
हमें न्यूनतम कैंडी की संख्या ढूंढनी होगी जो हमें देनी होगी?
तो यदि इनपुट [1,1,3] जैसा है, तो आउटपुट 4 होगा। तो उन्हें क्रमशः 1, 1 और 2 कैंडी मिलेगी।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
n := रेटिंग सरणी का आकार, आकार n की एक सरणी dp बनाएं, इसे 1 से भरें
ret := 0
i को 1 से n - 1 तक की रेंज में
यदि ratings[i] > ratings[i - 1], तो dp[i] := dp[i - 1] + 1
i को n - 2 से 0 तक नीचे की ओर
यदि ratings[i] > ratings[i + 1], तो dp[i] := dp[i] और dp[i + 1] + 1 का अधिकतम
ret := dp के तत्वों का योग
ret लौटाएं
उदाहरण (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
