# Leetcode Candy problem solution

In this Leetcode Candy problem solution, There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements:

1. Each child must have at least one candy.
2. Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

## Problem solution in Python.

```from itertools import *

class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
dp = [1] * n

for i in range(1, n):
if ratings[i] > ratings[i - 1] and dp[i] <= dp[i - 1]:
dp[i] = dp[i - 1] + 1

for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1] and dp[i] <= dp[i + 1]:
dp[i] = dp[i + 1] + 1

return sum(dp)
```

## Problem solution in Java.

```class Solution {
public int candy(int[] nums) {

int ans = 0;
int n = nums.length;
int[] candy = new int[n];

for(int i=nums.length-1;i>0;i--){
if(nums[i-1]>nums[i]){
candy[i-1] = candy[i]+1;
}
}

for(int i=0;i<nums.length-1;i++)
{
if(nums[i]<nums[i+1] && candy[i]>=candy[i+1])
{
candy[i+1] = candy[i]+1;
}
ans+=candy[i];
}

return n+ans+candy[n-1];
}
}
```

## Problem solution in C++.

```class Solution {
public:
int candy(vector<int>& a) {
int n = a.size();
vector<int>v(n,1);
for(int i=1;i<n;i++)
{
if(a[i]>a[i-1])
{
v[i] = v[i-1] + 1;
}
}
for(int i=n-2;i>=0;i--)
{
if(a[i]>a[i+1])
{
v[i] = max(v[i],v[i+1]+1);
}
}
int ans = 0;
for(auto i:v)
{
ans += i;
}
return ans;
}
};
```

## Problem solution in C.

```int data[100000];
int *ratings;
int n;

int fun(int p){
if(data[p]) return data[p];
data[p] = -0x7fffffff;
if(!p){
if(ratings[p] > ratings[p+1])
return fun(p+1)+1;
else
return data[p] = 1;
}
if(p == n-1){
if(ratings[p] > ratings[p-1])
return fun(p-1)+1;
else
return data[p] = 1;
}
if(ratings[p-1] >= ratings[p] && ratings[p+1] >= ratings[p]){
return data[p] = 1;
}else if(ratings[p-1] < ratings[p] && ratings[p+1] < ratings[p]){
int va = fun(p-1);
int vb = fun(p+1);
return data[p] = (va>vb?va:vb)+1;
}else if(ratings[p-1] < ratings[p] && ratings[p+1] >= ratings[p]){
return data[p] = fun(p-1)+1;
}else if(ratings[p-1] >= ratings[p] && ratings[p+1] < ratings[p]){
return data[p] = fun(p+1)+1;
}
return data[p];
}

int candy(int rating[], int len) {
ratings = rating;
memset(data,0,len*sizeof(int));
n = len;
int sum = 0;
for(int i = 0;i < n;i ++)
sum += fun(i);
return sum;
}
```