A subarray
A[i], A[i+1], ..., A[j]
ofA
is said to be turbulent if and only if:
- For
i <= k < j
,A[k] > A[k+1]
whenk
is odd, andA[k] < A[k+1]
whenk
is even;- OR, for
i <= k < j
,A[k] > A[k+1]
whenk
is even, andA[k] < A[k+1]
whenk
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
Approach #1: Math. [Java]
class Solution { public int maxTurbulenceSize(int[] A) { int len = A.length; int inc = 1, dec = 1, result = 1; for (int i = 1; i < len; ++i) { if (A[i] < A[i-1]) { dec = inc + 1; inc = 1; } else if (A[i] > A[i-1]) { inc = dec + 1; dec = 1; } else { inc = 1; dec = 1; } result = Math.max(result, Math.max(inc, dec)); } return result; } }
Analysis:
inc: denote the length of subarray with two increase elements;
dec: denote the length of subarray with two decrease elements;
Reference:
https://leetcode.com/problems/longest-turbulent-subarray/discuss/221935/Java-O(N)-time-O(1)-space