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
|
Input: [4,8,12,16]
Output: 2
|
Example 3:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class {
public int maxTurbulenceSize(int[] A) {
if (A.length <= 2) return A.length;
int maxLen = 0;
for (int i = 0; i < A.length - 1; i++) {
int count = 1;
for (int j = i; j < A.length - 1; j++) {
if (A[i] > A[i + 1]) {
if ((j - i) % 2 == 0 && A[j] > A[j + 1]) {
count++;
} else if ((j - i) % 2 == 1 && A[j] < A[j + 1]) {
count++;
} else if ((j - i) % 2 == 0 && A[j] <= A[j + 1]) {
break;
} else if ((j - i) % 2 == 1 && A[j] >= A[j + 1]) {
break;
}
} else if (A[i] < A[i + 1]) {
if ((j - i) % 2 == 0 && A[j] < A[j + 1]) {
count++;
} else if ((j - i) % 2 == 1 && A[j] > A[j + 1]) {
count++;
} else if ((j - i) % 2 == 0 && A[j] >= A[j + 1]) {
break;
} else if ((j - i) % 2 == 1 && A[j] <= A[j + 1]) {
break;
}
}
maxLen = count > maxLen?count:maxLen;
}
}
return maxLen;
}
}
|
近期评论