Length of the longest alternating increasing decreasing subarray
Given an array arr[], the task is to find the length of the longest alternating subarray.
A subarray {x1, x2, .. xn} is an alternating increasing decreasing sequence if its elements satisfy one of the following relations :
x1 < x2 > x3 < x4 > x5 < …. xn or
x1 > x2 < x3 > x4 < x5 > …. xn
Example:
Input: arr = {1, 2, 3, 2, 5, 6}
Output: 4
Explanation: The first elements form index 1 to 4 inclusive are alternating subarray – {2, 3, 2, 5}Input: arr = {5, 2, 1}
Output: 2
Naive Approach: The naive approach is to check for each subarray if the subarrays starting at every index are alternating. The idea is to use two nested for-loops.
Below is the implementation of the above approach
C++14
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; int maxAlternatingSubarray( int n, int * arr) { // Initialize mx to store maximum // length alternating subarrays int i, j, max = 1, count = 1, a, b; // Initialize a variable to check is the // subarray starts with greater // or smaller value bool check; // If length of the array is 1 // then return 1 if (n == 1) return 1; // Traverse for every element for (i = 0; i < n; i++) { // Reinitialize count to 1 as // at least one element is counted count = 1; // Subarray starting at every element for (j = i; j < n - 1; j++) { // Initialize a and b for storing // adjacent positions a = j; b = j + 1; // Check if the alternating subarray // starts with greater // or smaller element if (j == i) { // Smaller element starts first if (arr[a] < arr[b]) check = 1; // Greater element starts first else if (arr[a] > arr[b]) check = 0; } // If check is 1 then the next // element should be greater if (check && arr[a] < arr[b]) { // Increment count count++; } // If check is 0 then the next // element should be greater else if (!check && arr[a] > arr[b]) { // Increment count count++; } else break ; // Update the value of check check = !check; } // Update the maximum value of count if (max < count) max = count; } // Return the maximum length return max; } // Driver code int main() { // Initialize the array int arr[] = { 1, 2, 3, 2, 5, 7 }; int n = sizeof (arr) / sizeof (arr[0]); // Call the function and print the answer cout << maxAlternatingSubarray(n, arr); } |
Java
// Java code for the above approach import java.io.*; class GFG { static int maxAlternatingSubarray( int n, int [] arr) { // Initialize mx to store maximum // length alternating subarrays int i, j, max = 1 , count = 1 , a, b; // Initialize a variable to check is the // subarray starts with greater // or smaller value boolean check= false ; // If length of the array is 1 // then return 1 if (n == 1 ) return 1 ; // Traverse for every element for (i = 0 ; i < n; i++) { // Reinitialize count to 1 as // at least one element is counted count = 1 ; // Subarray starting at every element for (j = i; j < n - 1 ; j++) { // Initialize a and b for storing // adjacent positions a = j; b = j + 1 ; // Check if the alternating subarray // starts with greater // or smaller element if (j == i) { // Smaller element starts first if (arr[a] < arr[b]) check = true ; // Greater element starts first else if (arr[a] > arr[b]) check = false ; } // If check is 1 then the next // element should be greater if (check== true && arr[a] < arr[b]) { // Increment count count++; } // If check is 0 then the next // element should be greater else if (check== false && arr[a] > arr[b]) { // Increment count count++; } else break ; // Update the value of check check = !check; } // Update the maximum value of count if (max < count) max = count; } // Return the maximum length return max; } // Driver code public static void main (String[] args) { // Initialize the array int arr[] = { 1 , 2 , 3 , 2 , 5 , 7 }; int n = arr.length; // Call the function and print the answer System.out.println( maxAlternatingSubarray(n, arr)); } } // This code is contributed by Potta Lokesh |
Python3
# Python implementation of the above approach def maxAlternatingSubarray(n, arr): # Initialize mx to store maximum # length alternating subarrays max = 1 count = 1 a = 0 b = 0 # Initialize a variable to check is the # subarray starts with greater # or smaller value check = 0 # If length of the array is 1 # then return 1 if (n = = 1 ): return 1 ; # Traverse for every element for i in range (n): # Reinitialize count to 1 as # at least one element is counted count = 1 ; # Subarray starting at every element for j in range (i, n - 1 ): # Initialize a and b for storing # adjacent positions a = j; b = j + 1 ; # Check if the alternating subarray # starts with greater # or smaller element if (j = = i): # Smaller element starts first if (arr[a] < arr[b]): check = 1 ; # Greater element starts first elif (arr[a] > arr[b]): check = 0 ; # If check is 1 then the next # element should be greater if (check and arr[a] < arr[b]): # Increment count count + = 1 # If check is 0 then the next # element should be greater elif ( not check and arr[a] > arr[b]): # Increment count count + = 1 else : break ; # Update the value of check check = not check; # Update the maximum value of count if ( max < count): max = count; # Return the maximum length return max ; # Driver code # Initialize the array arr = [ 1 , 2 , 3 , 2 , 5 , 7 ]; n = len (arr); # Call the function and print the answer print (maxAlternatingSubarray(n, arr)); # This code is contributed by gfgking. |
C#
// C# code for the above approach using System; class GFG { static int maxAlternatingSubarray( int n, int []arr) { // Initialize mx to store maximum // length alternating subarrays int i, j, max = 1, count = 1, a, b; // Initialize a variable to check is the // subarray starts with greater // or smaller value bool check= false ; // If length of the array is 1 // then return 1 if (n == 1) return 1; // Traverse for every element for (i = 0; i < n; i++) { // Reinitialize count to 1 as // at least one element is counted count = 1; // Subarray starting at every element for (j = i; j < n - 1; j++) { // Initialize a and b for storing // adjacent positions a = j; b = j + 1; // Check if the alternating subarray // starts with greater // or smaller element if (j == i) { // Smaller element starts first if (arr[a] < arr[b]) check = true ; // Greater element starts first else if (arr[a] > arr[b]) check = false ; } // If check is 1 then the next // element should be greater if (check== true && arr[a] < arr[b]) { // Increment count count++; } // If check is 0 then the next // element should be greater else if (check== false && arr[a] > arr[b]) { // Increment count count++; } else break ; // Update the value of check check = !check; } // Update the maximum value of count if (max < count) max = count; } // Return the maximum length return max; } // Driver code public static void Main () { // Initialize the array int []arr = { 1, 2, 3, 2, 5, 7 }; int n = arr.Length; // Call the function and print the answer Console.Write(maxAlternatingSubarray(n, arr)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript implementation of the above approach function maxAlternatingSubarray(n, arr) { // Initialize mx to store maximum // length alternating subarrays let i, j, max = 1, count = 1, a, b; // Initialize a variable to check is the // subarray starts with greater // or smaller value let check; // If length of the array is 1 // then return 1 if (n == 1) return 1; // Traverse for every element for (i = 0; i < n; i++) { // Reinitialize count to 1 as // at least one element is counted count = 1; // Subarray starting at every element for (j = i; j < n - 1; j++) { // Initialize a and b for storing // adjacent positions a = j; b = j + 1; // Check if the alternating subarray // starts with greater // or smaller element if (j == i) { // Smaller element starts first if (arr[a] < arr[b]) check = 1; // Greater element starts first else if (arr[a] > arr[b]) check = 0; } // If check is 1 then the next // element should be greater if (check && arr[a] < arr[b]) { // Increment count count++; } // If check is 0 then the next // element should be greater else if (!check && arr[a] > arr[b]) { // Increment count count++; } else break ; // Update the value of check check = !check; } // Update the maximum value of count if (max < count) max = count; } // Return the maximum length return max; } // Driver code // Initialize the array let arr = [ 1, 2, 3, 2, 5, 7 ]; let n = arr.length; // Call the function and print the answer document.write(maxAlternatingSubarray(n, arr)); // This code is contributed by Samim Hossain Mondal. </script> |
4
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Approach: The given problem can be optimized by iterating the array and precomputing the difference between consecutive elements. Follow the steps below to solve the problem:
- Iterate the array from index 1 till the end and at every iteration:
- If the current element is greater than the previous element then increment currGreater by 1 and reset currSmaller to 0
- Else if the current element is smaller than the previous element then increment currSmaller by 1 and reset currGreater to 0
- Else if current and previous elements are equal then reset both currGreater and currSmaller to 0
- Swap the values of currGreater and currSmaller
- Update the value of maximum length by comparing it to currGreater and currSmaller
- Return the value of maximum length calculated
C++14
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate maximum length // of alternating subarray int longestAltSubarray( int N, int * arr) { // If length of the array is 1 // then return 1 if (N == 1) return 1; int maxLen = 0; int currGreater = 0, currSmaller = 0; // Traverse the temp array for ( int i = 1; i < N; i++) { // If current element is greater // than the previous element if (arr[i] > arr[i - 1]) { // Increment currGreater by 1 currGreater++; // Reset currSmaller to 0 currSmaller = 0; } // If current element is smaller // than the previous element else if (arr[i] < arr[i - 1]) { // Increment currSmaller by 1 currSmaller++; // Reset currGreater to 0 currGreater = 0; } // If current element is equal // to previous element else { // Reset both to 0 currGreater = 0; currSmaller = 0; } // Swap currGreater and currSmaller // for the next iteration int temp = currGreater; currGreater = currSmaller; currSmaller = temp; // Update maxLen maxLen = max(maxLen, max(currGreater, currSmaller)); } // Return the maximum length return maxLen + 1; } // Drivers code int main() { // Initialize the array int arr[] = { 1, 2, 3, 2, 5, 7 }; int n = sizeof (arr) / sizeof (arr[0]); // Call the function and print the answer cout << longestAltSubarray(n, arr); } |
Java
// Java implementation for the above approach import java.util.*; public class GFG { // Function to calculate maximum length // of alternating subarray static int longestAltSubarray( int N, int []arr) { // If length of the array is 1 // then return 1 if (N == 1 ) return 1 ; int maxLen = 0 ; int currGreater = 0 , currSmaller = 0 ; // Traverse the temp array for ( int i = 1 ; i < N; i++) { // If current element is greater // than the previous element if (arr[i] > arr[i - 1 ]) { // Increment currGreater by 1 currGreater++; // Reset currSmaller to 0 currSmaller = 0 ; } // If current element is smaller // than the previous element else if (arr[i] < arr[i - 1 ]) { // Increment currSmaller by 1 currSmaller++; // Reset currGreater to 0 currGreater = 0 ; } // If current element is equal // to previous element else { // Reset both to 0 currGreater = 0 ; currSmaller = 0 ; } // Swap currGreater and currSmaller // for the next iteration int temp = currGreater; currGreater = currSmaller; currSmaller = temp; // Update maxLen maxLen = Math.max(maxLen, Math.max(currGreater, currSmaller)); } // Return the maximum length return maxLen + 1 ; } // Drivers code public static void main(String args[]) { // Initialize the array int []arr = { 1 , 2 , 3 , 2 , 5 , 7 }; int n = arr.length; // Call the function and print the answer System.out.println(longestAltSubarray(n, arr)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 implementation for the above approach from builtins import range # Function to calculate maximum length # of alternating subarray def longestAltSubarray(N, arr): # If length of the array is 1 # then return 1 if (N = = 1 ): return 1 maxLen = 0 currGreater = 0 currSmaller = 0 # Traverse the temp array for i in range ( 1 , N, 1 ): # If current element is greater # than the previous element if (arr[i] > arr[i - 1 ]): # Increment currGreater by 1 currGreater + = 1 # Reset currSmaller to 0 currSmaller = 0 # If current element is smaller # than the previous element elif (arr[i] < arr[i - 1 ]): # Increment currSmaller by 1 currSmaller + = 1 # Reset currGreater to 0 currGreater = 0 # If current element is equal # to previous element else : # Reset both to 0 currGreater = 0 currSmaller = 0 # Swap currGreater and currSmaller # for the next iteration temp = currGreater currGreater = currSmaller currSmaller = temp # Update maxLen maxLen = max (maxLen, max (currGreater, currSmaller)) # Return the maximum length return maxLen + 1 # Driver code if __name__ = = '__main__' : # Initialize the array arr = [ 1 , 2 , 3 , 2 , 5 , 7 ] n = len (arr) # Call the function and print the answer print (longestAltSubarray(n, arr)) # This code is contributed by shikhasingrajput |
C#
// C# implementation for the above approach using System; class GFG { // Function to calculate maximum length // of alternating subarray static int longestAltSubarray( int N, int []arr) { // If length of the array is 1 // then return 1 if (N == 1) return 1; int maxLen = 0; int currGreater = 0, currSmaller = 0; // Traverse the temp array for ( int i = 1; i < N; i++) { // If current element is greater // than the previous element if (arr[i] > arr[i - 1]) { // Increment currGreater by 1 currGreater++; // Reset currSmaller to 0 currSmaller = 0; } // If current element is smaller // than the previous element else if (arr[i] < arr[i - 1]) { // Increment currSmaller by 1 currSmaller++; // Reset currGreater to 0 currGreater = 0; } // If current element is equal // to previous element else { // Reset both to 0 currGreater = 0; currSmaller = 0; } // Swap currGreater and currSmaller // for the next iteration int temp = currGreater; currGreater = currSmaller; currSmaller = temp; // Update maxLen maxLen = Math.Max(maxLen, Math.Max(currGreater, currSmaller)); } // Return the maximum length return maxLen + 1; } // Drivers code public static void Main() { // Initialize the array int []arr = { 1, 2, 3, 2, 5, 7 }; int n = arr.Length; // Call the function and print the answer Console.Write(longestAltSubarray(n, arr)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript implementation for the above approach // Function to calculate maximum length // of alternating subarray function longestAltSubarray(N, arr) { // If length of the array is 1 // then return 1 if (N == 1) return 1; let maxLen = 0; let currGreater = 0, currSmaller = 0; // Traverse the temp array for (let i = 1; i < N; i++) { // If current element is greater // than the previous element if (arr[i] > arr[i - 1]) { // Increment currGreater by 1 currGreater++; // Reset currSmaller to 0 currSmaller = 0; } // If current element is smaller // than the previous element else if (arr[i] < arr[i - 1]) { // Increment currSmaller by 1 currSmaller++; // Reset currGreater to 0 currGreater = 0; } // If current element is equal // to previous element else { // Reset both to 0 currGreater = 0; currSmaller = 0; } // Swap currGreater and currSmaller // for the next iteration let temp = currGreater; currGreater = currSmaller; currSmaller = temp; // Update maxLen maxLen = Math.max(maxLen, Math.max(currGreater, currSmaller)); } // Return the maximum length return maxLen + 1; } // Drivers code // Initialize the array let arr = [1, 2, 3, 2, 5, 7]; let n = arr.length // Call the function and let the answer document.write(longestAltSubarray(n, arr)) // This code is contributed by gfgking. </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us