Longest Turbulent Subarray

A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

• For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
• OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16]
Output: 2

Example 3:

Input: [100]
Output: 1

Note:

• 1 <= A.length <= 40000
• 0 <= A[i] <= 10^9

Solution

Solution 1: Sliding window (Dynamic)

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        m, beg, end = len(A), 0, 0
        last_diff, maxi = 0, -float("inf")
        
        while end < m-1:     
            curr_diff = A[end] - A[end+1]
            
            # If both are same sign, there is no turbulence.
            if (last_diff ^ curr_diff) >= 0:
                beg = end
                
            if curr_diff == 0: # Case: [9,9]
                beg = end + 1
                
            end += 1
            maxi = max(maxi, end-beg+1)
            last_diff = curr_diff
            
        return maxi if maxi != -float("inf") else m