135. Candy

class Solution {
    public int candy(int[] ratings) {
        int candies = 0, n = ratings.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        
        //Left relative array
        for(int i = 1; i < n; i++) {
            //If current index rating > previous ; give extra candies
            if(ratings[i] > ratings[i-1]) left[i] = left[i-1] + 1;
        }
        
        //Right relative array
        for(int i = n-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1]) right[i] = right[i+1] +1;
        }
        
       //Merge both the sides
        for(int i = 0; i < n; i++) {
            candies = candies + Math.max(left[i], right[i]);
        }
        
        return candies;
    }
}


class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1])
                candies[i] = candies[i - 1] + 1;
        }
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1])
                candies[i] = Math.max(candies[i], candies[i+1] +1);
        }
        int total = 0; 
        for(int candy : candies) 
            total+=candy;
        
        return total;
    }
}

class Solution {
    public int candy(int[] ratings) {
        if(ratings.length <= 1) return ratings.length;
        int candies = 0;
        int up = 0, down = 0; 
        int prevSlope = 0;
        
        for(int i = 1; i < ratings.length; i++) {
            //If increasing then 1; if decreasing then -1; if equal then 0.
            int currSlope = (ratings[i] > ratings[i-1]) ? 1 
                : (ratings[i] < ratings[i-1] ? -1 : 0);
            //                                       _
            //If mountain is changing. \_ || \/ ||  /
            if((prevSlope < 0 && currSlope >= 0) || (prevSlope > 0 && currSlope == 0)) {  
                candies = candies + sum(up) + sum(down) + (Math.max(up, down));
                System.out.println(up + " "+ down + " " +candies);
                up = 0; 
                down = 0;
            }
            
            //Add in up/down if slope is increasing or decreasing respectively. 
            //If it is a plain, add a candy as it is the base case.
            if(currSlope > 0) {
                up++;
            }
            else if(currSlope < 0) {
                down++;
            }
            else {
                candies++;
            }
            
            prevSlope = currSlope;
        } 
        System.out.println(up + " "+ down + " "+ candies);
        candies = candies + sum(up) + sum(down) + (Math.max(up, down) + 1);
        return candies;
    }
    
    int sum(int n) {
        return (n * (n + 1)) / 2;
    }
}