Problem statement

https://leetcode.com/problems/longest-turbulent-subarray/

Solution

Let us define dp(i, dr) is the longest turbulent subarray, which ends with position i and such that its last step was incresing if dr = 1 and decreasing if dr = -1. Then:

  1. if i == 0, answer is 1. Also if (A[i] - A[i-1]) * dr >= 0, it means that we can not continue the previous turbulent subarray, we also return 1.
  2. In the opposite case we return dp(i-1, -dr) + 1, where we change direction from dr to -dr.

Complexity

It is O(n), because we have O(n) states and each state processed in O(1).

Code

class Solution:
    def maxTurbulenceSize(self, A):
        
        @lru_cache(None)
        def dp(i, dr):
            if i == 0 or (A[i] - A[i-1])*dr >= 0: return 1
            return dp(i-1, -dr) + 1
        
        return max(dp(i, dr) for i in range(len(A)) for dr in [-1, 1])