O(n) space solution Simple to grasp


#1

Comint Solution::candy(vector &A) {
int n=A.size();
if(n<=1)
return n;
vector temp(n,1);
for(int i=1;i<n;i++)
{
if(A[i-1]<A[i])
{
temp[i]=temp[i-1]+1;
}
}
for(int i=n-1;i>0;i–)
{
if(A[i-1]>A[i])
{
temp[i-1]=max(temp[i]+1,temp[i-1]);
}
}
int ans=0;
for(int i=0;i<n;i++)
{
ans+=temp[i];
}
return ans;
}
ment body goes here.