Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/978.html
978. Longest Turbulent Subarray (Medium)
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]
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
Related Topics:
Array, Dynamic Programming, Sliding Window
Similar Questions:
Solution 1.
// OJ: https://leetcode.com/problems/longest-turbulent-subarray/
// Time: O(N)
// Space: O(1)
class Solution {
inline int getSign(int n) { return n > 0 ? 1 : (n == 0 ? 0 : -1); }
public:
int maxTurbulenceSize(vector<int>& A) {
if (A.size() == 1) return 1;
int sign = getSign(A[0] - A[1]), start = 0, ans = sign ? 2 : 1;
for (int i = 2; i < A.size(); ++i) {
int next = getSign(A[i - 1] - A[i]);
if (next * sign >= 0) start = i - 1;
else ans = max(ans, i - start + 1);
sign = next;
}
return ans;
}
};
-
class Solution { public int maxTurbulenceSize(int[] A) { if (A == null) return 0; int length = A.length; if (length < 2) return length; int start = 0; while (start < length - 1 && A[start] == A[start + 1]) start++; if (start == length - 1) return 1; int maxSize = 2; int difference = A[start + 1] - A[start]; if (difference > 0) difference = 1; else difference = -1; int index = start + 2; while (index < length) { int curDifference = A[index] - A[index - 1]; if (curDifference * difference >= 0) { maxSize = Math.max(maxSize, index - start); start = index - 1; while (start < length - 1 && A[start] == A[start + 1]) start++; if (start == length - 1) break; int nextDifference = A[start + 1] - A[start]; difference = nextDifference > 0 ? 1 : -1; index = start + 2; } else { index++; difference = -difference; } } maxSize = Math.max(maxSize, index - start); return maxSize; } } ############ class Solution { public int maxTurbulenceSize(int[] arr) { int ans = 1, f = 1, g = 1; for (int i = 1; i < arr.length; ++i) { int ff = arr[i - 1] < arr[i] ? g + 1 : 1; int gg = arr[i - 1] > arr[i] ? f + 1 : 1; f = ff; g = gg; ans = Math.max(ans, Math.max(f, g)); } return ans; } }
-
// OJ: https://leetcode.com/problems/longest-turbulent-subarray/ // Time: O(N) // Space: O(1) class Solution { public: int maxTurbulenceSize(vector<int>& A) { int inc = 1, dec = 1, N = A.size(), ans = 1; for (int i = 1; i < N; ++i) { if (A[i] == A[i - 1]) inc = dec = 1; else if (A[i] > A[i - 1]) { inc = dec + 1; dec = 1; } else { dec = inc + 1; inc = 1; } ans = max({ ans, inc, dec }); } return ans; } };
-
# 978. Longest Turbulent Subarray # https://leetcode.com/problems/longest-turbulent-subarray/ class Solution: def maxTurbulenceSize(self, arr: List[int]) -> int: n = len(arr) res = curr = 0 for i in range(n): if i >= 2 and ((arr[i - 2] > arr[i - 1] < arr[i]) or (arr[i - 2] < arr[i - 1] > arr[i])): curr += 1 elif i >= 1 and arr[i - 1] != arr[i]: curr = 2 else: curr = 1 res = max(res, curr) return res
-
func maxTurbulenceSize(arr []int) int { ans, f, g := 1, 1, 1 for i, x := range arr[1:] { ff, gg := 1, 1 if arr[i] < x { ff = g + 1 } if arr[i] > x { gg = f + 1 } f, g = ff, gg ans = max(ans, max(f, g)) } return ans } func max(a, b int) int { if a > b { return a } return b }
-
function maxTurbulenceSize(arr: number[]): number { let f = 1; let g = 1; let ans = 1; for (let i = 1; i < arr.length; ++i) { const ff = arr[i - 1] < arr[i] ? g + 1 : 1; const gg = arr[i - 1] > arr[i] ? f + 1 : 1; f = ff; g = gg; ans = Math.max(ans, f, g); } return ans; }