Given an array arr[] of N integers. The task is to find the maximum length of the longest increasing contiguous subarray after removing exactly one element from the given array.
Examples :
Input : N = 5, arr[] = { 2, 4, 1, 5, 7 }
Output : 4
Explanation : After removing third element from the array, the array arr[ ] becomes [2, 4, 5, 7] . therefore, the length of longest increasing contiguous subarray is 4, which is maximum.
Input : N = 4, arr[] = { 2, 1, 3, 1 }
Output : 2
Explanation : We can either remove the second or first element from the array, and the array, arr[ ] becomes {1, 3, 1} or {2, 3, 1}, and the length of longest increasing contiguous subarray is 2, which is maximum.
Approach: The task can be solved by keeping track of the longest increasing subsequence starting from index ‘i’, and also ending at index ‘i’.
- Create two arrays front[ ] and back[ ] of size N and initialize both arrays with 1.
- Calculate front[i] and back[i] for each i from 1 to N, where front[i] represents the maximum length of the longest increasing subsequence starting from the position i and back[i] represents the maximum length of the longest increasing subsequence ending at position i.
- The array front[ ] can be calculated in order from left to right with the following condition: if(a[i] > a[i-1]) update front[i] = front[i-1] + 1, else continue. In the same way, array back[ ] can be calculated in order from right to left with the following condition: if(a[i] < a[i+1]) update back[i] = back[i+1] + 1, else continue
- Now calculate the ans, initialized with 1, with these two arrays.
- Update ans if (a[i] < a[i+2]), it means (i+1)th element is getting deleted, same with back[] array.
Below is the implementation of the above approach:
C++
// c++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum length of longest// increasing contiguous subarray after removing// exactly one element from arrayint maxLenSubarr(int arr[], int n){ // Creating front[] and back[] arrays int front[n], back[n]; for (int i = 0; i < n; i++) { front[i] = 1; back[i] = 1; } // Calculating the front[] for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { // Update front[i] front[i] = front[i - 1] + 1; } } // Calculating the back[] for (int i = n - 2; i >= 0; i--) { if (arr[i] < arr[i + 1]) { // update back[i] back[i] = back[i + 1] + 1; } } // Store the length of longest increasing // contiguous subarray int ans = 1; // Check whether first element is // contributing in subarray or not bool check_first = true; // Keep track of longest subarray when // first element is removed int ans_first = 1; for (int i = 1; i < n; i++) { // front[i] == 1 means contribution of // first element in max // length subarray has ended if (front[i] == 1) { check_first = true; } ans_first = max(ans_first, front[i]); } // First element contributes in the subarray if (check_first == false) { ans_first -= 1; } // Check whether last element is // contributing in subarray or not bool check_last = true; // Keep track of longest subarray when // last element is removed int ans_last = 1; for (int i = n - 2; i >= 0; i--) { // back[i] == 1 means contribution of // last element in max // length subarray has ended if (back[i] == 1) { check_last = true; } ans_last = max(ans_last, back[i]); } // Last element contributes in the subarray if (check_last == false) { ans_last -= 1; } // Update ans ans = max(ans_first, ans_last); // Calculating max length when // (i+1)th element is deleted for (int i = 0; i < n - 2; i++) { if (arr[i] < arr[i + 2]) { ans = max(ans, front[i] + back[i + 2]); } } return ans;}// Driver codeint main(){ int arr[] = { 2, 1, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maxLenSubarr(arr, n); return 0;} |
C
// C program for the above approach#include <stdio.h>// increasing contiguous subarray after removingint maxLenSubarr(int arr[], int N){ // Creating front[] and back[] arrays int front[N], back[N]; for (int i = 0; i < N; i++) { front[i] = 1; back[i] = 1; } // Calculating the front[] for (int i = 1; i < N; i++) { if (arr[i] > arr[i - 1]) { // Updating the front[i] front[i] = front[i - 1] + 1; } } // Calculating the back[] for (int i = N - 2; i >= 0; i--) { if (arr[i] < arr[i + 1]) { // updating back[i] back[i] = back[i + 1] + 1; } } // Storing the length of longest increasing int ans = 1; // Check whether first element is int check_first = 1; // Keep track of longest subarray when int ans_first = 1; for (int i = 1; i < N; i++) { // front[i] == 1 means contribution of // first element in max if (front[i] == 1) { check_first = 1; } ans_first = ans_first > front[i] ? ans_first : front[i]; } // First element contributes in the subarray if (check_first == 0) { ans_first -= 1; } // contributing in subarray or not int check_last = 1; // Keep track of longest subarray when // last element is removed int ans_last = 1; for (int i = N - 2; i >= 0; i--) { // back[i] == 1 means contribution of // last element in max // length subarray has ended if (back[i] == 1) { check_last = 1; } ans_last = ans_last > back[i] ? ans_last : back[i]; } // Last element contributes in the subarray if (check_last == 0) { ans_last -= 1; } // Update answer ans = ans_first > ans_last ? ans_first : ans_last; // Calculating maximum length when for (int i = 0; i < N - 2; i++) { if (arr[i] < arr[i + 2]) { int temp = front[i] + back[i + 2]; if (temp > ans) { ans = temp; } } } return ans;}// Drive codeint main(){ int arr[] = { 2, 1, 3, 1 }; int N = sizeof(arr) / sizeof(arr[0]); printf("%d", maxLenSubarr(arr, N)); return 0;} |
Java
// Java program for the above approachpublic class GFG {// Function to find the maximum length of longest// increasing contiguous subarray after removing// exactly one element from arraystatic int maxLenSubarr(int arr[], int n){ // Creating front[] and back[] arrays int front[] = new int[n]; int back[] = new int[n]; for (int i = 0; i < n; i++) { front[i] = 1; back[i] = 1; } // Calculating the front[] for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { // Update front[i] front[i] = front[i - 1] + 1; } } // Calculating the back[] for (int i = n - 2; i >= 0; i--) { if (arr[i] < arr[i + 1]) { // update back[i] back[i] = back[i + 1] + 1; } } // Store the length of longest increasing // contiguous subarray int ans = 1; // Check whether first element is // contributing in subarray or not boolean check_first = true; // Keep track of longest subarray when // first element is removed int ans_first = 1; for (int i = 1; i < n; i++) { // front[i] == 1 means contribution of // first element in max // length subarray has ended if (front[i] == 1) { check_first = true; } ans_first = Math.max(ans_first, front[i]); } // First element contributes in the subarray if (check_first == false) { ans_first -= 1; } // Check whether last element is // contributing in subarray or not boolean check_last = true; // Keep track of longest subarray when // last element is removed int ans_last = 1; for (int i = n - 2; i >= 0; i--) { // back[i] == 1 means contribution of // last element in max // length subarray has ended if (back[i] == 1) { check_last = true; } ans_last = Math.max(ans_last, back[i]); } // Last element contributes in the subarray if (check_last == false) { ans_last -= 1; } // Update ans ans = Math.max(ans_first, ans_last); // Calculating max length when // (i+1)th element is deleted for (int i = 0; i < n - 2; i++) { if (arr[i] < arr[i + 2]) { ans = Math.max(ans, front[i] + back[i + 2]); } } return ans;} // Driver code public static void main (String[] args) { int arr[] = { 2, 1, 3, 1 }; int n = arr.length; System.out.println(maxLenSubarr(arr, n)); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the maximum length of longest# increasing contiguous subarray after removing# exactly one element from arraydef maxLenSubarr(arr, n) : # Creating front[] and back[] arrays front = [0] * n; back = [0] * n; for i in range(n) : front[i] = 1; back[i] = 1; # Calculating the front[] for i in range(1, n) : if (arr[i] > arr[i - 1]) : # Update front[i] front[i] = front[i - 1] + 1; # Calculating the back[] for i in range(n - 2, -1, -1) : if (arr[i] < arr[i + 1]) : # update back[i] back[i] = back[i + 1] + 1; # Store the length of longest increasing # contiguous subarray ans = 1; # Check whether first element is # contributing in subarray or not check_first = True; # Keep track of longest subarray when # first element is removed ans_first = 1; for i in range(1, n) : # front[i] == 1 means contribution of # first element in max # length subarray has ended if (front[i] == 1) : check_first = True; ans_first = max(ans_first, front[i]); # First element contributes in the subarray if (check_first == False) : ans_first -= 1; # Check whether last element is # contributing in subarray or not check_last = True; # Keep track of longest subarray when # last element is removed ans_last = 1; for i in range(n - 2, -1, -1) : # back[i] == 1 means contribution of # last element in max # length subarray has ended if (back[i] == 1) : check_last = True; ans_last = max(ans_last, back[i]); # Last element contributes in the subarray if (check_last == False) : ans_last -= 1; # Update ans ans = max(ans_first, ans_last); # Calculating max length when # (i+1)th element is deleted for i in range( n - 2) : if (arr[i] < arr[i + 2]) : ans = max(ans, front[i] + back[i + 2]); return ans;# Driver codeif __name__ == "__main__" : arr = [ 2, 1, 3, 1 ]; n = len(arr); print(maxLenSubarr(arr, n)); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;public class GFG {// Function to find the maximum length of longest// increasing contiguous subarray after removing// exactly one element from arraystatic int maxLenSubarr(int []arr, int n){ // Creating front[] and back[] arrays int []front = new int[n]; int []back = new int[n]; for (int i = 0; i < n; i++) { front[i] = 1; back[i] = 1; } // Calculating the front[] for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { // Update front[i] front[i] = front[i - 1] + 1; } } // Calculating the back[] for (int i = n - 2; i >= 0; i--) { if (arr[i] < arr[i + 1]) { // update back[i] back[i] = back[i + 1] + 1; } } // Store the length of longest increasing // contiguous subarray int ans = 1; // Check whether first element is // contributing in subarray or not bool check_first = true; // Keep track of longest subarray when // first element is removed int ans_first = 1; for (int i = 1; i < n; i++) { // front[i] == 1 means contribution of // first element in max // length subarray has ended if (front[i] == 1) { check_first = true; } ans_first = Math.Max(ans_first, front[i]); } // First element contributes in the subarray if (check_first == false) { ans_first -= 1; } // Check whether last element is // contributing in subarray or not bool check_last = true; // Keep track of longest subarray when // last element is removed int ans_last = 1; for (int i = n - 2; i >= 0; i--) { // back[i] == 1 means contribution of // last element in max // length subarray has ended if (back[i] == 1) { check_last = true; } ans_last = Math.Max(ans_last, back[i]); } // Last element contributes in the subarray if (check_last == false) { ans_last -= 1; } // Update ans ans = Math.Max(ans_first, ans_last); // Calculating max length when // (i+1)th element is deleted for (int i = 0; i < n - 2; i++) { if (arr[i] < arr[i + 2]) { ans = Math.Max(ans, front[i] + back[i + 2]); } } return ans;} // Driver code public static void Main(string[] args) { int []arr = { 2, 1, 3, 1 }; int n = arr.Length; Console.WriteLine(maxLenSubarr(arr, n)); }}// This code is contributed by AnkThon |
Javascript
//javascript code for above approachfunction maxLenSubarr(arr, n) { // Creating front[] and back[] arrays let front = new Array(n).fill(1); let back = new Array(n).fill(1); // Calculating the front[] for (let i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { // Update front[i] front[i] = front[i - 1] + 1; } } // Calculating the back[] for (let i = n - 2; i >= 0; i--) { if (arr[i] < arr[i + 1]) { // Update back[i] back[i] = back[i + 1] + 1; } } // Store the length of longest increasing // contiguous subarray let ans = 1; // Check whether first element is // contributing in subarray or not let check_first = true; // Keep track of longest subarray when // first element is removed let ans_first = 1; for (let i = 1; i < n; i++) { // front[i] == 1 means contribution of // first element in max length subarray // has ended if (front[i] == 1) { check_first = true; } ans_first = Math.max(ans_first, front[i]); } // First element contributes in the subarray if (check_first == false) { ans_first -= 1; } // Check whether last element is // contributing in subarray or not let check_last = true; // Keep track of longest subarray when // last element is removed let ans_last = 1; for (let i = n - 2; i >= 0; i--) { // back[i] == 1 means contribution of // last element in max length subarray // has ended if (back[i] == 1) { check_last = true; } ans_last = Math.max(ans_last, back[i]); } // Last element contributes in the subarray if (check_last == false) { ans_last -= 1; } // Update ans ans = Math.max(ans_first, ans_last); // Calculating max length when (i+1)th element is deleted for (let i = 0; i < n - 2; i++) { if (arr[i] < arr[i + 2]) { ans = Math.max(ans, front[i] + back[i + 2]); } } return ans;}// Driver codelet arr = [2, 1, 3, 1];let n = arr.length;console.log(maxLenSubarr(arr, n)); |
Output
2
Time complexity: O(N)
Auxiliary Space: O(N)
Approach 2: Using the two Pointers
Algorithm steps:
- Initialize two pointers left and right to the start of the array.
- Initialize a variable maxLen to 1 to keep track of the length of the longest increasing subarray.
- Initialize a variable currLen to 1 to keep track of the length of the current increasing subarray.
- Move the right pointer to the next element.
- If the current element is greater than the previous element, increment currLen.
- If the current element is not greater than the previous element, update maxLen if currLen is greater than maxLen, reset currLen to 1 and move the left pointer to the current position of right.
- Repeat steps 4-6 until the right pointer reaches the end of the array.
- Update maxLen if currLen is greater than maxLen.
- Return maxLen.
Below is the implementation of the above approach:
C++
//C++ code for the above approach#include <stdio.h>// using two pointers to find the longest increasing subarrayint maxLenSubarr(int arr[], int N){ int left = 0, right = 1, currLen = 1, maxLen = 1; while (right < N) { if (arr[right] > arr[right-1]) { currLen++; } else { if (currLen > maxLen) { maxLen = currLen; } currLen = 1; left = right; } right++; } if (currLen > maxLen) { maxLen = currLen; } return maxLen;}// Drive codeint main(){ int arr[] = { 2, 1, 3, 1 }; int N = sizeof(arr) / sizeof(arr[0]); printf("%d", maxLenSubarr(arr, N)); return 0;} |
Python3
# Function to find the length of the longest increasing subarraydef maxLenSubarr(arr, N): left = 0 # Initialize the left pointer right = 1 # Initialize the right pointer currLen = 1 # Initialize the current length maxLen = 1 # Initialize the maximum length # Loop through the array while right < N: if arr[right] > arr[right - 1]: currLen += 1 # Increment current length if the next element is greater else: if currLen > maxLen: maxLen = currLen # Update maximum length if needed currLen = 1 # Reset current length left = right # Move the left pointer to the right pointer right += 1 if currLen > maxLen: maxLen = currLen # Check and update maximum length one more time return maxLen# Driver codeif __name__ == "__main__": arr = [2, 1, 3, 1] N = len(arr) print(maxLenSubarr(arr, N)) |
Javascript
// Function to find the length of the longest increasing subarrayfunction GFG(arr) { let left = 0; let right = 1; let currLen = 1; let maxLen = 1; while (right < arr.length) { if (arr[right] > arr[right - 1]) { currLen++; } else { if (currLen > maxLen) { maxLen = currLen; } currLen = 1; left = right; } right++; } if (currLen > maxLen) { maxLen = currLen; } return maxLen;}// Driver codeconst arr = [2, 1, 3, 1];const result = GFG(arr);console.log(result); // Output: 2 |
Output
2
Time complexity: O(N), where N is the length of the input array.
Auxiliary Space: O(N), where N is the length of the input array.
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!
