Saturday 10 October 2015

MORENA



Morenas Candy Shop ( Easy )

Link to the question : MORENA

HINT :

Think of dp solution. We check if a[i] is > or < or = a[i-1] and store its relative sign in another array, b[i]. Now just count the number of times the sign alternates.

RECOMMENDED QUESTION :

Try solving this dp question .

SOURCE CODE :

#include<stdio.h>
long long int a[1000010];
int b[1000010];
int main()
{
    int n,i;
    scanf("%d",&n);
    b[0] = 0;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        if(i>0)
        {
            if(a[i]>a[i-1])
                b[i] = 1;
            else if(a[i] < a[i-1])
                b[i] = -1;
            else
                b[i] = 0;
        }
    }
    int c=1,sign=0;
    for(i=1;i<n;i++)
    {
        if((sign == 0) && (b[i] != 0))
        {
               c++;
               sign = b[i];
        }
        else if((sign ==1) && (b[i]== -1))
        {
            c++;
            sign = b[i];
        }
        else if((sign == -1) && (b[i] == 1))
        {
            c++;
            sign = b[i];
        }
    }
    printf("%d\n",c);
    return 0;
}

1 comment: