Sponsored
Sponsored
In this approach, a sliding window technique is used to identify the longest turbulent subarray. We maintain two pointers: 'start' and 'end'. Initially, 'start' is set to 0, and 'end' is used to iterate over the array. At each step, we check the relationship between consecutive elements to determine the turbulence. When the pattern breaks, we calculate the length of the turbulent segment and adjust the pointers accordingly.
Time Complexity: O(n), where n is the length of the array, as the solution involves a single pass over the array.
Space Complexity: O(1), as it uses a constant amount of extra space.
1#include <vector>
2using namespace std;
3int maxTurbulenceSize(vector<int>& arr) {
4 int n = arr.size();
5 if (n < 2) return n;
6 int max_len = 1, current_len = 1;
7 for (int i = 1; i < n; ++i) {
8 if (arr[i - 1] < arr[i]) {
9 current_len = (i % 2 == 0) ? 2 : 1;
10 } else if (arr[i - 1] > arr[i]) {
11 current_len = (i % 2 == 1) ? 2 : 1;
12 } else {
13 current_len = 1;
14 }
15 max_len = max(max_len, current_len);
16 }
17 return max_len;
18}This C++ solution utilizes a similar approach to the C implementation, but leverages C++ STL's max function for cleaner code and operates over a vector.
This approach utilizes dynamic programming to maintain two arrays: inc and dec, which record the lengths of increasing and decreasing turbulent subarrays that end at each index. The solution updates these values based on the conditions of the current element relative to the previous one, and tracks the global maximum using the values in inc and dec.
Time Complexity: O(n), as the array is traversed once.
Space Complexity: O(1), minimal additional space is used.
This Python function employs dynamic programming logic to evaluate the turbulent pattern. Two variables, inc and dec, capture subarray lengths, updated dynamically on each iteration.