Algorithm
Problem Name: 978. Longest Turbulent Subarray
Given an integer array arr, return the length of a maximum size turbulent subarray of arr.
A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:
- For
i <= k < j:arr[k] > arr[k + 1]whenkis odd, andarr[k] < arr[k + 1]whenkis even.
- Or, for
i <= k < j:arr[k] > arr[k + 1]whenkis even, andarr[k] < arr[k + 1]whenkis odd.
Example 1:
Input: arr = [9,4,2,10,7,8,8,1,9] Output: 5 Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
Example 2:
Input: arr = [4,8,12,16] Output: 2
Example 3:
Input: arr = [100] Output: 1
Constraints:
1 <= arr.length <= 4 * 1040 <= arr[i] <= 109
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const maxTurbulenceSize = function(arr) {
const n = arr.length
return Math.max(helper(), helper1())
// < > <
function helper() {
const cnt = Array(n).fill(1)
for(let i = 0; i < n - 1; i++) {
if(i % 2 === 1 && arr[i] > arr[i + 1]) {
cnt[i + 1] = cnt[i] + 1
} else if(i % 2 === 0 && arr[i] < arr[i + 1]) {
cnt[i + 1] = cnt[i] + 1
}
}
return Math.max(...cnt)
}
function helper1() {
const cnt = Array(n).fill(1)
for(let i = 0; i < n - 1; i++) {
if(i % 2 === 1 && arr[i] < arr[i + 1] > {
cnt[i + 1] = cnt[i] + 1
} else if(i % 2 === 0 && arr[i] > arr[i + 1] ) {
cnt[i + 1] = cnt[i] + 1
}
}
return Math.max(...cnt)
}
};
Input
arr = [9,4,2,10,7,8,8,1,9]
Output
5
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxTurbulenceSize(self, A):
arr = [A[i - 1] < A[i] for i in range(1, len(A))]
cur = mx = 1 + (len(A) > 1)
for i in range(1, len(arr)):
if A[i] != A[i + 1] and arr[i] != arr[i - 1]:
cur += 1
mx = max(cur, mx)
else:
cur = 2
return mx
Input
arr = [9,4,2,10,7,8,8,1,9]
Output
5