Given an array arr[] of N integers. The task is to find the length of the contiguous strictly decreasing sequence that can be derived after removing at most one element from the array arr[].
Examples
Input: arr[] = {8, 7, 3, 5, 2, 9}
Output: 4
Explanation:
If we remove 3, The maximum length of decreasing sequence is 4 and the sequence is { 8, 7, 5, 2 }
If we remove 5, The maximum length of decreasing sequence is 4 and the sequence is { 8, 7, 3, 2 }
In both removal we get 4 as the maximum length.
Input: arr[] = {1, 2, 9, 8, 3, 7, 6, 4}
Output: 5
Approach:
- Create two arrays, left[] which stores the length of decreasing sequence from left to right and right[] which stores the length of decreasing sequence from right to left.
- Traverse the given array arr[].
- If previous element(arr[i-1]) is greater than the next element(arr[i+1]), then check whether removing that element will give the maximum length of decreasing subsequence or not.
- Update the maximum length of decreasing subsequence.
Below is the implementation of the above approach:
C++
// C++ program to find maximum length// of decreasing sequence by removing// at most one element#include <bits/stdc++.h>using namespace std;// Function to find the maximum lengthint maxLength(int* a, int n){ // Initialise maximum length to 1 int maximum = 1; // Initialise left[] to find the // length of decreasing sequence // from left to right int left[n]; // Initialise right[] to find the // length of decreasing sequence // from right to left int right[n]; // Initially store 1 at each index of // left and right array for (int i = 0; i < n; i++) { left[i] = 1; right[i] = 1; } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the right array for (int i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { right[i] = right[i + 1] + 1; } // Store the length of longest // continuous decreasing // sequence in maximum maximum = max(maximum, right[i]); } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the left array for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { left[i] = left[i - 1] + 1; } } if (n > 2) { // Check if we can obtain a // longer decreasing sequence // after removal of any element // from the array arr[] with // the help of left[] & right[] for (int i = 1; i < n - 1; i++) { if (a[i - 1] > a[i + 1]) { maximum = max(maximum, left[i - 1] + right[i + 1]); } } } // Return maximum length of sequence return maximum;}// Driver codeint main(){ int arr[6] = { 8, 7, 3, 5, 2, 9 }; int n = sizeof(arr) / sizeof(arr[0]); // Function calling cout << maxLength(arr, n) << endl; return 0;} |
Java
// Java program to find maximum length // of decreasing sequence by removing // at most one element class GFG { // Function to find the maximum length static int maxLength(int []a, int n) { // Initialise maximum length to 1 int maximum = 1; // Initialise left[] to find the // length of decreasing sequence // from left to right int left [] = new int[n]; // Initialise right[] to find the // length of decreasing sequence // from right to left int right[] = new int[n]; // Initially store 1 at each index of // left and right array for (int i = 0; i < n; i++) { left[i] = 1; right[i] = 1; } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the right array for (int i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { right[i] = right[i + 1] + 1; } // Store the length of longest // continuous decreasing // sequence in maximum maximum = Math.max(maximum, right[i]); } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the left array for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { left[i] = left[i - 1] + 1; } } if (n > 2) { // Check if we can obtain a // longer decreasing sequence // after removal of any element // from the array arr[] with // the help of left[] & right[] for (int i = 1; i < n - 1; i++) { if (a[i - 1] > a[i + 1]) { maximum = Math.max(maximum, left[i - 1] + right[i + 1]); } } } // Return maximum length of sequence return maximum; } // Driver code public static void main (String[] args) { int arr[] = { 8, 7, 3, 5, 2, 9 }; int n = arr.length; // Function calling System.out.println(maxLength(arr, n)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 program to find maximum length # of decreasing sequence by removing # at most one element # Function to find the maximum length def maxLength(a, n) : # Initialise maximum length to 1 maximum = 1; # Initialise left[] to find the # length of decreasing sequence # from left to right left = [0]*n; # Initialise right[] to find the # length of decreasing sequence # from right to left right = [0]*n; # Initially store 1 at each index of # left and right array for i in range(n) : left[i] = 1; right[i] = 1; # Iterate over the array arr[] to # store length of decreasing # sequence that can be obtained # at every index in the right array for i in range(n - 2, -1, -1) : if (a[i] > a[i + 1]) : right[i] = right[i + 1] + 1; # Store the length of longest # continuous decreasing # sequence in maximum maximum = max(maximum, right[i]); # Iterate over the array arr[] to # store length of decreasing # sequence that can be obtained # at every index in the left array for i in range(1, n) : if (a[i] < a[i - 1]) : left[i] = left[i - 1] + 1; if (n > 2) : # Check if we can obtain a # longer decreasing sequence # after removal of any element # from the array arr[] with # the help of left[] & right[] for i in range(1, n -1) : if (a[i - 1] > a[i + 1]) : maximum = max(maximum, left[i - 1] + right[i + 1]); # Return maximum length of sequence return maximum; # Driver code if __name__ == "__main__" : arr = [ 8, 7, 3, 5, 2, 9 ]; n = len(arr); # Function calling print(maxLength(arr, n)); # This code is contributed by AnkitRai01 |
C#
// C# program to find maximum length // of decreasing sequence by removing // at most one element using System;class GFG { // Function to find the maximum length static int maxLength(int []a, int n) { // Initialise maximum length to 1 int maximum = 1; // Initialise left[] to find the // length of decreasing sequence // from left to right int []left = new int[n]; // Initialise right[] to find the // length of decreasing sequence // from right to left int []right = new int[n]; // Initially store 1 at each index of // left and right array for (int i = 0; i < n; i++) { left[i] = 1; right[i] = 1; } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the right array for (int i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { right[i] = right[i + 1] + 1; } // Store the length of longest // continuous decreasing // sequence in maximum maximum = Math.Max(maximum, right[i]); } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the left array for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { left[i] = left[i - 1] + 1; } } if (n > 2) { // Check if we can obtain a // longer decreasing sequence // after removal of any element // from the array arr[] with // the help of left[] & right[] for (int i = 1; i < n - 1; i++) { if (a[i - 1] > a[i + 1]) { maximum = Math.Max(maximum, left[i - 1] + right[i + 1]); } } } // Return maximum length of sequence return maximum; } // Driver code public static void Main (String[] args) { int []arr = { 8, 7, 3, 5, 2, 9 }; int n = arr.Length; // Function calling Console.WriteLine(maxLength(arr, n)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript program to find maximum length// of decreasing sequence by removing// at most one element// Function to find the maximum lengthfunction maxLength(a, n){ // Initialise maximum length to 1 let maximum = 1; // Initialise left[] to find the // length of decreasing sequence // from left to right let left = new Array(n); // Initialise right[] to find the // length of decreasing sequence // from right to left let right = new Array(n); // Initially store 1 at each index of // left and right array for (let i = 0; i < n; i++) { left[i] = 1; right[i] = 1; } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the right array for (let i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { right[i] = right[i + 1] + 1; } // Store the length of longest // continuous decreasing // sequence in maximum maximum = Math.max(maximum, right[i]); } // Iterate over the array arr[] to // store length of decreasing // sequence that can be obtained // at every index in the left array for (let i = 1; i < n; i++) { if (a[i] < a[i - 1]) { left[i] = left[i - 1] + 1; } } if (n > 2) { // Check if we can obtain a // longer decreasing sequence // after removal of any element // from the array arr[] with // the help of left[] & right[] for (let i = 1; i < n - 1; i++) { if (a[i - 1] > a[i + 1]) { maximum = Math.max(maximum, left[i - 1] + right[i + 1]); } } } // Return maximum length of sequence return maximum;}// Driver codelet arr = [ 8, 7, 3, 5, 2, 9 ];let n = arr.length;// Function callingdocument.write(maxLength(arr, n) + "<br>");// This code is contributed by gfgking</script> |
Output:
4
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
