My c code , O(N) 13ms


  • 0
    8
    int data[100000];
    int *ratings;
    int n;
    
    int fun(int p){
        if(data[p]) return data[p];
        data[p] = -0x7fffffff;
        if(!p){
            if(ratings[p] > ratings[p+1])
                return fun(p+1)+1;
            else
                return data[p] = 1;
        }
        if(p == n-1){
            if(ratings[p] > ratings[p-1])
                return fun(p-1)+1;
            else
                return data[p] = 1;
        }
        if(ratings[p-1] >= ratings[p] && ratings[p+1] >= ratings[p]){
            return data[p] = 1;
        }else if(ratings[p-1] < ratings[p] && ratings[p+1] < ratings[p]){
            int va = fun(p-1);
            int vb = fun(p+1);
            return data[p] = (va>vb?va:vb)+1;
        }else if(ratings[p-1] < ratings[p] && ratings[p+1] >= ratings[p]){
            return data[p] = fun(p-1)+1;
        }else if(ratings[p-1] >= ratings[p] && ratings[p+1] < ratings[p]){
            return data[p] = fun(p+1)+1;
        }
        return data[p];
    }
    
    int candy(int rating[], int len) {
        ratings = rating;
        memset(data,0,len*sizeof(int));
        n = len;
        int sum = 0;
        for(int i = 0;i < n;i ++)
            sum += fun(i);
        return sum;
    }`enter code here`

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.