Simple and easy to understand C++ solution : O(n) complexity


#1
int Solution::candy(vector<int> &A) {
    int n = A.size();
    if (n == 0)
        return 0;
    vector<int> dp1(n, 1), dp2(n, 1);
    // dp1 represents the minimum number of candies to give, considering the left neighbours
    // dp2 represents the minimum number of candies to give, considering the right neighbours
    for (int i = 1; i < n ; i++){
        if (A[i] > A[i-1]){
            dp1[i] = dp1[i-1] + 1;
        }
    }
    for (int i = n-2 ; i >= 0 ; i-- ){
        if (A[i] > A[i+1]){
            dp2[i] = dp2[i+1] + 1;
        }
    }
    int ans = 0;
    for (int i = 0 ; i < n ; i++){
        // for a particular index i, the minimum no. of candies to be given out, should the max of 
        // minimum no. of candies considering the left neighbour and the right neighbour.
        ans += max(dp1[i], dp2[i]) ;
    }
    return ans;
}