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 <stdio.h>
2int maxTurbulenceSize(int* arr, int arrSize) {
3 if (arrSize < 2) return arrSize;
4 int max_len = 1, current_len = 1;
5 for (int i = 1; i < arrSize; ++i) {
6 if (arr[i - 1] < arr[i]) {
7 current_len = (i % 2 == 0) ? 2 : 1;
8 } else if (arr[i - 1] > arr[i]) {
9 current_len = (i % 2 == 1) ? 2 : 1;
10 } else {
11 current_len = 1;
12 }
13 max_len = (current_len > max_len) ? current_len : max_len;
14 }
15 return max_len;
16}This C implementation iterates over the array, checking each adjacent pair of elements to determine if they are part of a turbulent sequence. It adjusts the length of the current turbulent subarray accordingly and keeps track of the maximum found so far.
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.
1 public int MaxTurbulenceSize(int[] arr) {
int inc = 1, dec = 1, max_len = 1;
for (int i = 1; i < arr.Length; ++i) {
if (arr[i - 1] < arr[i]) {
inc = dec + 1;
dec = 1;
} else if (arr[i - 1] > arr[i]) {
dec = inc + 1;
inc = 1;
} else {
inc = dec = 1;
}
max_len = Math.Max(max_len, Math.Max(inc, dec));
}
return max_len;
}
}This C# code captures the process of retracing turbulent lengths using two counters. Each step evaluates current array indices to derive increment or decrement series.