[LeetCode] Longest Turbulent Subarray

Problem: Given an integer array arr, return the length of a maximum size turbulent subarray of arr.

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

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:

• For i <= k < j:
• arr[k] > arr[k + 1] when k is odd, and
• arr[k] < arr[k + 1] when k is even.
• Or, for i <= k < j:
• arr[k] > arr[k + 1] when k is even, and
• arr[k] < arr[k + 1] when k is odd.

Example:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

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

Input: arr = [100]
Output: 1

Approach: The approach is same as the approach which we have taken to solve the problem of finding the sub array with maximum sum in the array i.e. Kadane algorithm. There we reset the current window when we find the current window's sum is less than 0, here we will reset the window when our pattern is broken. That's all!

Implementation in C#:

    public int MaxTurbulenceSize(int[] arr) 

    {

        int length = arr?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        int start = 0;

        int maxLength = 1;

        for (int i = 1; i < length; ++i)

        {

            int currCompare = arr[i - 1].CompareTo(arr[i]);

            if (currCompare == 0)

            {

                start = i;

            }

            else if (i == length - 1 || currCompare * arr[i].CompareTo(arr[i + 1]) != -1)

            {

                maxLength = Math.Max(maxLength, i - start + 1);

                start = i;

            }

        }

        return maxLength;

    }

Complexity: O(n)