BinarySearch 0239 Fair Pay

Problem statement

https://binarysearch.com/problems/Fair-Pay/

Solution

Equal to Leetcode 0135. Candy.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, R):
        n, ans = len(R), [1]*len(R)
        
        for i in range(n-1):
            if R[i] < R[i+1]:
                ans[i+1] = max(1 + ans[i], ans[i+1])
                
        for i in range(n-2, -1, -1):
            if R[i+1] < R[i]:
                ans[i] = max(1 + ans[i+1], ans[i])
        
        return sum(ans)