# candy

## candy

### Greedy approach

I meet this problem from hackrank one years before, at that time I did not resolve it. We need to consider two directions for each person and give him some candys. Think each direcion seprerately. Each person, give hime a candys from left, and give him b candys from right. The minnum candys we should give hime is max(a,b). Otherwise, if you try to meet the condictions, some one will be given zero or less candys.

```
1 class Solution {
2 public:
3 int candy(vector<int> &ratings) {
4 int n = ratings.size();
5 if ( n == 0 ) {
6 return 0;
7 }
8 int l[n];
9 int r[n];
10 memset(l,0,sizeof(l));
11 memset(r,0,sizeof(r));
12 l[0] = 1;
13 r[n-1] = 1;
14 for( int i = 1; i < n; i++ ) {
15 int j = (n-1)-i;
16 if ( ratings[i] > ratings[i-1] ) {
17 l[i] = l[i-1]+1;
18 } else {
19 l[i] = 1;
20 }
21 if ( ratings[j] > ratings[j+1] ) {
22 r[j] = r[j+1]+1;
23 } else {
24 r[j] = 1;
25 }
26 }
27 int sum = 0;
28 for ( int i = 0; i < n; i++ ) {
29 sum += max(l[i],r[i]);
30 }
31 return sum;
32 }
33 };
```

### A better way

The solutions before needs two array, and actually only one is needed. The second time travel the ratings we can get the answer already.

```
1 class Solution {
2 public:
3 int candy(vector<int> &ratings) {
4 int n = ratings.size();
5 int t[n];
6 memset(t,0,sizeof(t));
7 t[0] = 1;
8 for ( int i = 1; i < n; i++ ) {
9 if ( ratings[i] > ratings[i-1] ) {
10 t[i] = t[i-1]+1;
11 } else {
12 t[i] = 1;
13 }
14 }
15 int now = 1;
16 int sum = max(1,t[n-1]);
17 for ( int i = n-2; i >= 0; i-- ) {
18 if ( ratings[i] > ratings[i+1] ) {
19 now += 1;
20 } else {
21 now = 1;
22 }
23 sum += max(now,t[i]);
24 }
25 return sum;
26 }
27 };
```