I think this O(n) recursive solution is easy to understand.

```
class Solution {
public:
int candyHelper(vector<int>& ratings, vector<int>& nums, int idx, int N){
if( nums[idx] != 0 )
return nums[idx];
int low = 0; int high = 0;
if( idx == 0 ) low = high = idx + 1;
else if( idx == N-1) low = high = idx - 1;
else{
if( ratings[idx-1] <= ratings[idx+1] ){
low = idx - 1; high = idx +1;}
else{
low = idx + 1; high = idx-1;
}
}
if( ratings[idx] <= ratings[low])
nums[idx] = 1;
else if ( ratings[idx] <= ratings[high])
nums[idx] = candyHelper(ratings, nums, low, N) + 1;
else
nums[idx] = max(candyHelper(ratings, nums, low, N),candyHelper(ratings, nums, high, N)) + 1;
return nums[idx];
}
int candy(vector<int> &ratings) {
int N = ratings.size();
if( N == 0) return 0;
if( N == 1) return 1;
vector<int> nums(N,0);
int sum = 0;
for( int i = 0; i < N; i++){
sum += candyHelper(ratings, nums, i, N);
}
return sum;
}
```