O(n) sol with comments


#1
int Solution::candy(vector<int> &A) {
    //algo
    //find local minimas
    //expand in both direction assigning max(ans[i],curr)
    //stop at A[i+1]<A[i] && A[i-1]<A[i]
    
    int n = A.size();
    if(n==0)return 0;
    if(n==1)return 1;
    
    vector<int>mins(n,0);
    vector<int>ans(n,1);
    
    //finding  local min
    if(A[0]<=A[1])mins[0] = 1;
    for(int i=1;i<n-1;i++)
    {
        if(A[i-1]>=A[i]&&A[i]<=A[i+1])mins[i]=1;
    }
    if(A[n-1]<=A[n-2])mins[n-1] = 1;
    
    //expansion
    int j;
    for(int i=0;i<n;i++)
    {
        
        if(mins[i]==1)
        {
            //expansion left
            j = i;
            while(j>0&&A[j-1]>A[j])
            {
                ans[j-1] = max(ans[j]+1,ans[j-1]);
                j--;
            }
            
            //expansion right
            j = i;
            while(j<n-1&&A[j+1]>A[j])
            {
                ans[j+1] = max(ans[j]+1,ans[j+1]);
                j++;
            }
        }
    }
    
    //total candies
    int res = 0;
    for(int i=0;i<n;i++)res+=ans[i];
    
    return res;
}