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, andA[k] < A[k+1]when k is even; - OR, for
i <= k < j, A[k] > A[k+1]when k is even, andA[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: [8,5,1,7,6,8,7,1,9]
Output: 6
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5] >A[6])
Note:
- 1 <= A.length <= 40000
- 0 <= A[i] <= 10^9
Solution:
To find the maximum subarray possible we will traverse the array once using a sliding window. Comparison can be made using -1,0,1 in place of (<,=,>). Since we only have to take care of the countings so using these techniques will reduce our complexity efficiently. So, the subarray with the longest [-1,1-1,1…] will be our answer.
Implementation:
bool isPosL(vector<int>&arr, int ind, int low)
{
bool res = true;
if(ind-2 >= low)
{
return (arr[ind-1] > arr[ind] && arr[ind-1] > arr[ind-2]) ||(arr[ind-1] < arr[ind] && arr[ind-1] < arr[ind-2]);
}
else
{
return ind>low ? arr[ind] != arr[ind-1] : true;
}
return res;
}
int maxTurbulenceSize(vector<int>& A) {
if(A.size() == 0 || A.size() == 1)
return A.size();
int i=0,j=0;
int len = 1;
while(j<A.size())
{
while(j<A.size() && isPosL(A,j,i))
{
len = std::max(len,j-i+1);
j++;
}
if(i!=j-1)
i = j-1;
else
i = j;
}
return len;
}
public int maxTurbulenceSize(int[] A) {
int l = 0;
int r = 1;
int maxLen = 1;
long lastDiff = 0;
while (r < A.length) {
int newDiff = A[r] - A[r - 1];
if (newDiff * lastDiff > 0) {
l = r - 1;
} else if (A[r] == A[r - 1]) {
l = r;
}
maxLen = Math.max(maxLen, r - l + 1);
lastDiff = newDiff;
r++;
}
return maxLen;
}
}
def maxTurbulenceSize(arr):
start = 0
max_length = 0
for index in range(1, len(arr)):
comp = cmp(arr[index-1], arr[index])
if comp == 0:
start = index
elif index != len(arr) - 1 and comp*cmp(arr[index], arr[index + 1]) != -1:
max_length = max(max_length, index + 1 - start)
start = index
return max(max_length, len(arr) - start)
