Simple DP Solution (O(n) space and O(n) time)


#1
int Distribute(int st, vector<int> &ans, vector<int> &A){
   if(ans[st] > 0LL)
       return ans[st];
   int v = 0, n = A.size();
   if((st < n - 1) && (A[st] > A[st + 1]))
       v = max(v, Distribute(st + 1, ans, A));
   if((st > 0) && (A[st] > A[st - 1]))
       v = max(v, Distribute(st - 1, ans, A));
   return ans[st] = v + 1;
}

int Solution::candy(vector<int> &A) {
      int n = A.size();
   vector<int> ans(n, 0);
   for(int i = 0; i < n; i ++)
       Distribute(i, ans, A);
   int s = 0;
   for(int i = 0; i < n; i ++)
       s += ans[i];
   return s;
}