Problem:
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 <= A.length <= 40000
0 <= A[i] <= 10^9
Solution:
We can use a pointer mark the start position of a turbulent subarray, then move the tail of turbulent subarray one step at a time. At each step, we compare the current value with previous and next value to check if we can move the tail one step further. If we can not move the tail further, the current position is the end of a turbulent subarray and the start of the next turbulent subarray. So calculate the length of the previous turbulent subarray, then we move the starting point here to mark the beginning of the next turbulent subarray. The problem's difficulty is in the details of no changing sequence, we need to consider the special case of 1, 1, 1, 1, 1, 1, 1, 1. The solution should return 1 instead of 2.
class Solution {
public static void main(String...args) {
int[] arr = new int[]{3};
System.out.println(solve(arr));
}
private static int solve(int[] arr) {
int start = 0;
int result = 1; //2
if(arr.length == 1) return 1;
//8 8 8 8 8 8 8 8
for(int i = 1; i < arr.length; i++) { //9,4,2,10,7,8,8,1,9
if(i == arr.length - 1 || (Integer.compare(arr[i], arr[i-1]) * Integer.compare(arr[i+1], arr[i]) >= 0)) {
if((arr[i] - arr[i-1]) != 0) {
result = Math.max(result, i - start + 1);
}
start = i;
}
}
return result;
}
}
public static void main(String...args) {
int[] arr = new int[]{3};
System.out.println(solve(arr));
}
private static int solve(int[] arr) {
int start = 0;
int result = 1; //2
if(arr.length == 1) return 1;
//8 8 8 8 8 8 8 8
for(int i = 1; i < arr.length; i++) { //9,4,2,10,7,8,8,1,9
if(i == arr.length - 1 || (Integer.compare(arr[i], arr[i-1]) * Integer.compare(arr[i+1], arr[i]) >= 0)) {
if((arr[i] - arr[i-1]) != 0) {
result = Math.max(result, i - start + 1);
}
start = i;
}
}
return result;
}
}
The time complexity is O(N) because we iterate the array only once, the space complexity is O(1).
