Formatted question description: https://leetcode.ca/all/978.html

978. Longest Turbulent Subarray (Medium)

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. 1 <= A.length <= 40000
  2. 0 <= A[i] <= 10^9

Related Topics:
Array, Dynamic Programming, Sliding Window

Similar Questions:

Solution 1.

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

// Time: O(N)
// Space: O(1)
class Solution {
    inline int getSign(int n) { return n > 0 ? 1 : (n == 0 ? 0 : -1); }
public:
    int maxTurbulenceSize(vector<int>& A) {
        if (A.size() == 1) return 1;
        int sign = getSign(A[0] - A[1]), start = 0, ans = sign ? 2 : 1;
        for (int i = 2; i < A.size(); ++i) {
            int next = getSign(A[i - 1] - A[i]);
            if (next * sign >= 0) start = i - 1;
            else ans = max(ans, i - start + 1);
            sign = next;
        }
        return ans;
    }
};

Java

class Solution {
    public int maxTurbulenceSize(int[] A) {
        if (A == null)
            return 0;
        int length = A.length;
        if (length < 2)
            return length;
        int start = 0;
        while (start < length - 1 && A[start] == A[start + 1])
            start++;
        if (start == length - 1)
            return 1;
        int maxSize = 2;
        int difference = A[start + 1] - A[start];
        if (difference > 0)
            difference = 1;
        else
            difference = -1;
        int index = start + 2;
        while (index < length) {
            int curDifference = A[index] - A[index - 1];
            if (curDifference * difference >= 0) {
                maxSize = Math.max(maxSize, index - start);
                start = index - 1;
                while (start < length - 1 && A[start] == A[start + 1])
                    start++;
                if (start == length - 1)
                    break;
                int nextDifference = A[start + 1] - A[start];
                difference = nextDifference > 0 ? 1 : -1;
                index = start + 2;
            } else {
                index++;
                difference = -difference;
            }
        }
        maxSize = Math.max(maxSize, index - start);
        return maxSize;
    }
}

All Problems

All Solutions