Longest increasing sequence possible by the boundary elements of an Array
Given an array arr[] of length N consisting of positive integers, the task is to find the longest increasing subsequence that can be formed by the elements from either end of the array.
Examples :
Input: N=4 arr[] ={ 1, 4, 2, 3 }
Output: 1 3 4
Explanation:
Append arr[0] to the sequence. Sequence = {1}. Array = {4, 2, 3}.
Append arr[2] to the sequence. Sequence = {1, 3}. Array = {4, 2}.
Append arr[0] to the sequence. Sequence = {1, 3, 4}. Array = {2}.
Therefore, {1, 3, 4} is the longest increasing sequence possible from the given array.Input: N=3 arr[] ={ 4, 1, 3 }
Output: 3 4
Approach: The idea to solve this problem is to use two pointer approach. Maintain a variable, say rightmost_element, for the rightmost element in the strictly increasing sequence. Keep two pointers at the ends of the array, say i and j respectively and perform the following steps until i surpasses j or elements at both ends are smaller than rightmost_element:
- If arr[i] > arr[j]:
- If arr[j] > rightmost_element: Set rightmost_element = arr[j] and decrement j. Add arr[j] to sequence.
- If arr[i] > rightmost_element: Set rightmost_element = arr[i] and increment i. Add arr[i] to sequence.
- If arr[i] < arr[j]:
- If arr[i] > rightmost_element: Set rightmost_element = arr[i] and increment i. Add arr[i] to sequence.
- If arr[j] > rightmost_element: Set rightmost_element = arr[j] and decrement j. Add arr[j] to sequence.
- If arr[j] = arr[i]:
- If i = j:
- If arr[i]>rightmost_element : Add arr[i] to sequence.
- Otherwise: Check the maximum elements that can be added from the two ends respectively, Let them be max_left and max_right respectively.
- If max_left > max_right: Add all the elements that can be added from the left end.
- Otherwise: Add all the elements that can be added from the right side.
- If i = j:
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> #include <vector> using namespace std; // Function to find longest strictly // increasing sequence using boundary elements void findMaxLengthSequence( int N, int arr[4]) { // Maintains rightmost element // in the sequence int rightmost_element = -1; // Pointer to start of array int i = 0; // Pointer to end of array int j = N - 1; // Stores the required sequence vector< int > sequence; // Traverse the array while (i <= j) { // If arr[i]>arr[j] if (arr[i] > arr[j]) { // If arr[j] is greater than // rightmost element of the sequence if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.push_back(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.push_back(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } else break ; } // If arr[i] < arr[j] else if (arr[i] < arr[j]) { // If arr[i] > rightmost element if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.push_back(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } // If arr[j] > rightmost element else if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.push_back(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else break ; } // If arr[i] is equal to arr[j] else if (arr[i] == arr[j]) { // If i and j are at the same element if (i == j) { // If arr[i] > rightmostelement if (arr[i] > rightmost_element) { // Push arr[j] into the sequence sequence.push_back(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } break ; } else { sequence.push_back(arr[i]); // Traverse array // from left to right int k = i + 1; // Stores the increasing // sequence from the left end vector< int > max_left; // Traverse array from left to right while (k < j && arr[k] > arr[k - 1]) { // Push arr[k] to max_left vector max_left.push_back(arr[k]); k++; } // Traverse the array // from right to left int l = j - 1; // Stores the increasing // sequence from the right end vector< int > max_right; // Traverse array from right to left while (l > i && arr[l] > arr[l + 1]) { // Push arr[k] to max_right vector max_right.push_back(arr[l]); l--; } // If size of max_left is greater // than max_right if (max_left.size() > max_right.size()) for ( int element : max_left) // Push max_left elements to // the original sequence sequence.push_back(element); // Otherwise else for ( int element : max_right) // Push max_right elements to // the original sequence sequence.push_back(element); break ; } } } // Print the sequence for ( int element : sequence) printf ( "%d " , element); } // Driver Code int main() { int N = 4; int arr[] = { 1, 3, 2, 1 }; // Print the longest increasing // sequence using boundary elements findMaxLengthSequence(N, arr); } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find longest strictly // increasing sequence using boundary elements static void findMaxLengthSequence( int N, int [] arr) { // Maintains rightmost element // in the sequence int rightmost_element = - 1 ; // Pointer to start of array int i = 0 ; // Pointer to end of array int j = N - 1 ; // Stores the required sequence Vector<Integer> sequence = new Vector<Integer>(); // Traverse the array while (i <= j) { // If arr[i]>arr[j] if (arr[i] > arr[j]) { // If arr[j] is greater than // rightmost element of the sequence if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.add(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.add(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } else break ; } // If arr[i] < arr[j] else if (arr[i] < arr[j]) { // If arr[i] > rightmost element if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.add(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } // If arr[j] > rightmost element else if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.add(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else break ; } // If arr[i] is equal to arr[j] else if (arr[i] == arr[j]) { // If i and j are at the same element if (i == j) { // If arr[i] > rightmostelement if (arr[i] > rightmost_element) { // Push arr[j] into the sequence sequence.add(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } break ; } else { sequence.add(arr[i]); // Traverse array // from left to right int k = i + 1 ; // Stores the increasing // sequence from the left end Vector<Integer> max_left = new Vector<Integer>(); // Traverse array from left to right while (k < j && arr[k] > arr[k - 1 ]) { // Push arr[k] to max_left vector max_left.add(arr[k]); k++; } // Traverse the array // from right to left int l = j - 1 ; // Stores the increasing // sequence from the right end Vector<Integer> max_right = new Vector<Integer>(); // Traverse array from right to left while (l > i && arr[l] > arr[l + 1 ]) { // Push arr[k] to max_right vector max_right.add(arr[l]); l--; } // If size of max_left is greater // than max_right if (max_left.size() > max_right.size()) for ( int element : max_left) // Push max_left elements to // the original sequence sequence.add(element); // Otherwise else for ( int element : max_right) // Push max_right elements to // the original sequence sequence.add(element); break ; } } } // Print the sequence for ( int element : sequence) System.out.print(element + " " ); } // Driver Code public static void main(String[] args) { int N = 4 ; int [] arr = { 1 , 3 , 2 , 1 }; // Print the longest increasing // sequence using boundary elements findMaxLengthSequence(N, arr); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach # Function to find longest strictly # increasing sequence using boundary elements def findMaxLengthSequence(N, arr): # Maintains rightmost element # in the sequence rightmost_element = - 1 # Pointer to start of array i = 0 # Pointer to end of array j = N - 1 # Stores the required sequence sequence = [] # Traverse the array while (i < = j): # If arr[i]>arr[j] if (arr[i] > arr[j]): # If arr[j] is greater than # rightmost element of the sequence if (arr[j] > rightmost_element): # Push arr[j] into the sequence sequence.append(arr[j]) # Update rightmost element rightmost_element = arr[j] j - = 1 elif (arr[i] > rightmost_element): # Push arr[i] into the sequence sequence.append(arr[i]) # Update rightmost element rightmost_element = arr[i] i + = 1 else : break # If arr[i] < arr[j] elif (arr[i] < arr[j]): # If arr[i] > rightmost element if (arr[i] > rightmost_element): # Push arr[i] into the sequence sequence.append(arr[i]) # Update rightmost element rightmost_element = arr[i] i + = 1 # If arr[j] > rightmost element elif (arr[j] > rightmost_element): # Push arr[j] into the sequence sequence.append(arr[j]) # Update rightmost element rightmost_element = arr[j] j - = 1 else : break # If arr[i] is equal to arr[j] elif (arr[i] = = arr[j]): # If i and j are at the same element if (i = = j): # If arr[i] > rightmostelement if (arr[i] > rightmost_element): # Push arr[j] into the sequence sequence.append(arr[i]) # Update rightmost element rightmost_element = arr[i] i + = 1 break else : sequence.append(arr[i]) # Traverse array # from left to right k = i + 1 # Stores the increasing # sequence from the left end max_left = [] # Traverse array from left to right while (k < j and arr[k] > arr[k - 1 ]): # Push arr[k] to max_left vector max_left.append(arr[k]) k + = 1 # Traverse the array # from right to left l = j - 1 # Stores the increasing # sequence from the right end max_right = [] # Traverse array from right to left while (l > i and arr[l] > arr[l + 1 ]): # Push arr[k] to max_right vector max_right.append(arr[l]) l - = 1 # If size of max_left is greater # than max_right if ( len (max_left) > len (max_right)): for element in max_left: # Push max_left elements to # the original sequence sequence.append(element) # Otherwise else : for element in max_right: # Push max_right elements to # the original sequence sequence.append(element) break # Print the sequence for element in sequence: print (element, end = " " ) # Driver Code if __name__ = = '__main__' : N = 4 arr = [ 1 , 3 , 2 , 1 ] # Print the longest increasing # sequence using boundary elements findMaxLengthSequence(N, arr) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find longest strictly // increasing sequence using boundary elements static void findMaxLengthSequence( int N, int [] arr) { // Maintains rightmost element // in the sequence int rightmost_element = -1; // Pointer to start of array int i = 0; // Pointer to end of array int j = N - 1; // Stores the required sequence List< int > sequence = new List< int >(); // Traverse the array while (i <= j) { // If arr[i]>arr[j] if (arr[i] > arr[j]) { // If arr[j] is greater than // rightmost element of the sequence if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.Add(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.Add(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } else break ; } // If arr[i] < arr[j] else if (arr[i] < arr[j]) { // If arr[i] > rightmost element if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.Add(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } // If arr[j] > rightmost element else if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.Add(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else break ; } // If arr[i] is equal to arr[j] else if (arr[i] == arr[j]) { // If i and j are at the same element if (i == j) { // If arr[i] > rightmostelement if (arr[i] > rightmost_element) { // Push arr[j] into the sequence sequence.Add(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } break ; } else { sequence.Add(arr[i]); // Traverse array // from left to right int k = i + 1; // Stores the increasing // sequence from the left end List< int > max_left = new List< int >(); // Traverse array from left to right while (k < j && arr[k] > arr[k - 1]) { // Push arr[k] to max_left vector max_left.Add(arr[k]); k++; } // Traverse the array // from right to left int l = j - 1; // Stores the increasing // sequence from the right end List< int > max_right = new List< int >(); // Traverse array from right to left while (l > i && arr[l] > arr[l + 1]) { // Push arr[k] to max_right vector max_right.Add(arr[l]); l--; } // If size of max_left is greater // than max_right if (max_left.Count > max_right.Count) foreach ( int element in max_left) // Push max_left elements to // the original sequence sequence.Add(element); // Otherwise else foreach ( int element in max_right) // Push max_right elements to // the original sequence sequence.Add(element); break ; } } } // Print the sequence foreach ( int element in sequence) Console.Write(element + " " ); } // Driver code static void Main() { int N = 4; int [] arr = { 1, 3, 2, 1 }; // Print the longest increasing // sequence using boundary elements findMaxLengthSequence(N, arr); } } // This code is contribute by divyesh072019 |
Javascript
<script> // Javascript program for the above approach // Function to find longest strictly // increasing sequence using boundary elements function findMaxLengthSequence(N, arr) { // Maintains rightmost element // in the sequence let rightmost_element = -1; // Pointer to start of array let i = 0; // Pointer to end of array let j = N - 1; // Stores the required sequence let sequence = []; // Traverse the array while (i <= j) { // If arr[i]>arr[j] if (arr[i] > arr[j]) { // If arr[j] is greater than // rightmost element of the sequence if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.push(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.push(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } else break ; } // If arr[i] < arr[j] else if (arr[i] < arr[j]) { // If arr[i] > rightmost element if (arr[i] > rightmost_element) { // Push arr[i] into the sequence sequence.push(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } // If arr[j] > rightmost element else if (arr[j] > rightmost_element) { // Push arr[j] into the sequence sequence.push(arr[j]); // Update rightmost element rightmost_element = arr[j]; j--; } else break ; } // If arr[i] is equal to arr[j] else if (arr[i] == arr[j]) { // If i and j are at the same element if (i == j) { // If arr[i] > rightmostelement if (arr[i] > rightmost_element) { // Push arr[j] into the sequence sequence.push(arr[i]); // Update rightmost element rightmost_element = arr[i]; i++; } break ; } else { sequence.push(arr[i]); // Traverse array // from left to right let k = i + 1; // Stores the increasing // sequence from the left end let max_left = []; // Traverse array from left to right while (k < j && arr[k] > arr[k - 1]) { // Push arr[k] to max_left vector max_left.push(arr[k]); k++; } // Traverse the array // from right to left let l = j - 1; // Stores the increasing // sequence from the right end let max_right = []; // Traverse array from right to left while (l > i && arr[l] > arr[l + 1]) { // Push arr[k] to max_right vector max_right.push(arr[l]); l--; } // If size of max_left is greater // than max_right if (max_left.length > max_right.length) for (let element = 0; element < max_left.length; element++) // Push max_left elements to // the original sequence sequence.push(max_left[element]); // Otherwise else for (let element = 0; element < max_right.length; element++) // Push max_right elements to // the original sequence sequence.push(max_right[element]); break ; } } } // Print the sequence for (let element = 0; element < sequence.length; element++) document.write(sequence[element] + " " ); } // Driver code let N = 4; let arr = [ 1, 3, 2, 1 ]; // Print the longest increasing // sequence using boundary elements findMaxLengthSequence(N, arr); // This code is contributed by suresh07 </script> |
1 2 3
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us