135. Candy

class Solution:
    def candy(self, ratings: List[int]) -> int:
        """
        main idea: two arrays to cache one side variation seperately and get the upper bound 
      tc O(N) sc O(N)  
        """
        
        n = len(ratings)
        left = [1] * n
        right = [1]* n
        for i in range(1,n):
            if ratings[i] > ratings[i-1]:
                left[i] = left[i-1] + 1
            
        for j in range(n-2,-1,-1):
            if ratings[j] >  ratings[j+1]:
                right[j] = right[j+1] + 1
        res = 0
        for k in range(n):
            res += max(left[k],right[k])
        return res 

class Solution:
    def candy(self, ratings: List[int]) -> int:
        """
        main idea: one arrays to 1. get left side 2. get best value when run right side by comparing with previous left round value 
      tc O(N) sc O(N)  
        """
        
        n = len(ratings)
        A = [1] * n
        # left 
        for i in range(1,n):
            if ratings[i] > ratings[i-1]:
                A[i] = A[i-1] + 1
        res = A[-1]  # note with initial of res    
        for j in range(n-2,-1,-1):
            if ratings[j] >  ratings[j+1]:
                A[j] = max(A[j],A[j+1] + 1)
            res += A[j] # can update res since it's last time to update A[j]
        return res