C ++中的Candy

假设有N个孩子，他们排成一行。在此为每个孩子分配一个评估值。我们向符合以下要求的这些儿童提供糖果-

• 每个孩子必须至少吃一个糖果。

• 评分较高的孩子比邻居得到的糖果更多。

我们必须找到我们必须给予的最少数量的糖果吗？

因此，如果输入类似于[1,1,3]，则输出将为4。因此，它们将分别获得1、1和2个糖果。

为了解决这个问题，我们将遵循以下步骤-

• n：=数组等级的大小，创建大小为n的称为dp的数组，使用1填充

• ret：= 0

• 当我在1到n – 1的范围内时

• 如果等级[i]>等级[i – 1]，则dp [i]：= dp [i-1] + 1

• 当我在n-2范围内降至0

• 如果等级[i]>等级[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