Problem description:

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:

1
2
3
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:

1
2
3
Input: [4,8,12,16]

Output: 2

Example 3:

1
2
Input: [100]
Output: 1

Note:

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

Solution:

Keep track of the current run length and the best run length. If the last three elements are turbulent, increase the current run length by 1. Otherwise, reset the run length.
We reset the run length to 1 if the previous and current elements are the same (Ex: [2,2,2,2,2]), or reset the run length to 2 if the previous and current elements are different (Ex: [2,4,6,8]). Return the length of the best run found.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int res= 0, cur= 0;
        for(int i= 0; i< A.size(); i++){
            if(i >= 2 && (A[i-2] > A[i-1] && A[i] > A[i-1]) ||
                          (A[i-2] < A[i-1] && A[i] < A[i-1])){
                cur++;
                // If the last three elements are turbulent, increment run length by 1.
            }
            else if(i >= 1 && A[i] != A[i-1])
                cur= 2;
                // The last three elements are not turbulent, so we'll reset the run length.
                // If the previous and current elements are not equal, the new run length is 2.
            else
                cur= 1;
                // Otherwise, the new run length is 1.
            res= max(res, cur);
        }
        return res;
    }
};

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/h3ZDKL