Given an array arr[] of length N with unique elements, the task is to find the length of the longest increasing subsequence that can be formed by the elements from either end of the array.
Examples:
Input: arr[] = {3, 5, 1, 4, 2}
Output: 4
Explanation:
The longest sequence is: {2, 3, 4, 5}
Pick 2, Sequence is {2}, Array is {3, 5, 1, 4}
Pick 3, Sequence is {2, 3}, Array is {5, 1, 4}
Pick 4, Sequence is {2, 3, 4}, Array is {5, 1}
Pick 5, Sequence is {2, 3, 4, 5}, Array is {1}
Input: arr[] = {3, 1, 5, 2, 4}
Output: 2
The longest sequence is {3, 4}
Approach: This problem can be solved by Two Pointer Approach. Set two pointers at the first and last indices of the array. Select the minimum of the two values currently pointed and check if it is greater than the previously selected value. If so, update the pointer and increase the length of the LIS and repeat the process. Otherwise, print the length of the LIS obtained.
Below is the implementation of the above approach:
C++
// C++ Program to print the// longest increasing// subsequence from the// boundary elements of an array#include <bits/stdc++.h>using namespace std;// Function to return the length of// Longest Increasing subsequenceint longestSequence(int n, int arr[]){ // Set pointers at // both ends int l = 0, r = n - 1; // Stores the recent // value added to the // subsequence int prev = INT_MIN; // Stores the length of // the subsequence int ans = 0; while (l <= r) { // Check if both elements // can be added to the // subsequence if (arr[l] > prev && arr[r] > prev) { if (arr[l] < arr[r]) { ans += 1; prev = arr[l]; l += 1; } else { ans += 1; prev = arr[r]; r -= 1; } } // Check if the element // on the left can be // added to the // subsequence only else if (arr[l] > prev) { ans += 1; prev = arr[l]; l += 1; } // Check if the element // on the right can be // added to the // subsequence only else if (arr[r] > prev) { ans += 1; prev = arr[r]; r -= 1; } // If none of the values // can be added to the // subsequence else { break; } } return ans;}// Driver Codeint main(){ int arr[] = { 3, 5, 1, 4, 2 }; // Length of array int n = sizeof(arr) / sizeof(arr[0]); cout << longestSequence(n, arr); return 0;} |
Java
// Java program to print the longest // increasing subsequence from the// boundary elements of an arrayimport java.util.*;class GFG{// Function to return the length of// Longest Increasing subsequencestatic int longestSequence(int n, int arr[]){ // Set pointers at // both ends int l = 0, r = n - 1; // Stores the recent // value added to the // subsequence int prev = Integer.MIN_VALUE; // Stores the length of // the subsequence int ans = 0; while (l <= r) { // Check if both elements // can be added to the // subsequence if (arr[l] > prev && arr[r] > prev) { if (arr[l] < arr[r]) { ans += 1; prev = arr[l]; l += 1; } else { ans += 1; prev = arr[r]; r -= 1; } } // Check if the element on the // left can be added to the // subsequence only else if (arr[l] > prev) { ans += 1; prev = arr[l]; l += 1; } // Check if the element on the // right can be added to the // subsequence only else if (arr[r] > prev) { ans += 1; prev = arr[r]; r -= 1; } // If none of the values // can be added to the // subsequence else { break; } } return ans;}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 5, 1, 4, 2 }; // Length of array int n = arr.length; System.out.print(longestSequence(n, arr));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to print the# longest increasing subsequence# from the boundary elements # of an arrayimport sys# Function to return the length of# Longest Increasing subsequencedef longestSequence(n, arr): # Set pointers at # both ends l = 0 r = n - 1 # Stores the recent value # added to the subsequence prev = -sys.maxsize - 1 # Stores the length of # the subsequence ans = 0 while (l <= r): # Check if both elements can be # added to the subsequence if (arr[l] > prev and arr[r] > prev): if (arr[l] < arr[r]): ans += 1 prev = arr[l] l += 1 else: ans += 1 prev = arr[r] r -= 1 # Check if the element # on the left can be # added to the # subsequence only elif (arr[l] > prev): ans += 1 prev = arr[l] l += 1 # Check if the element # on the right can be # added to the # subsequence only elif (arr[r] > prev): ans += 1 prev = arr[r] r -= 1 # If none of the values # can be added to the # subsequence else: break return ans # Driver codearr = [ 3, 5, 1, 4, 2 ]# Length of arrayn = len(arr)print(longestSequence(n, arr))# This code is contributed by sanjoy_62 |
C#
// C# program to print the longest // increasing subsequence from the// boundary elements of an arrayusing System;class GFG{// Function to return the length of// longest Increasing subsequencestatic int longestSequence(int n, int []arr){ // Set pointers at // both ends int l = 0, r = n - 1; // Stores the recent value // added to the subsequence int prev = int.MinValue; // Stores the length of // the subsequence int ans = 0; while (l <= r) { // Check if both elements // can be added to the // subsequence if (arr[l] > prev && arr[r] > prev) { if (arr[l] < arr[r]) { ans += 1; prev = arr[l]; l += 1; } else { ans += 1; prev = arr[r]; r -= 1; } } // Check if the element on the // left can be added to the // subsequence only else if (arr[l] > prev) { ans += 1; prev = arr[l]; l += 1; } // Check if the element on the // right can be added to the // subsequence only else if (arr[r] > prev) { ans += 1; prev = arr[r]; r -= 1; } // If none of the values // can be added to the // subsequence else { break; } } return ans;}// Driver Codepublic static void Main(String[] args){ int []arr = { 3, 5, 1, 4, 2 }; // Length of array int n = arr.Length; Console.Write(longestSequence(n, arr));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript Program to print the// longest increasing// subsequence from the// boundary elements of an array// Function to return the length of// Longest Increasing subsequencefunction longestSequence(n, arr){ // Set pointers at // both ends var l = 0, r = n - 1; // Stores the recent // value added to the // subsequence var prev = -1000000000; // Stores the length of // the subsequence var ans = 0; while (l <= r) { // Check if both elements // can be added to the // subsequence if (arr[l] > prev && arr[r] > prev) { if (arr[l] < arr[r]) { ans += 1; prev = arr[l]; l += 1; } else { ans += 1; prev = arr[r]; r -= 1; } } // Check if the element // on the left can be // added to the // subsequence only else if (arr[l] > prev) { ans += 1; prev = arr[l]; l += 1; } // Check if the element // on the right can be // added to the // subsequence only else if (arr[r] > prev) { ans += 1; prev = arr[r]; r -= 1; } // If none of the values // can be added to the // subsequence else { break; } } return ans;}// Driver Codevar arr = [ 3, 5, 1, 4, 2 ];// Length of arrayvar n = arr.length;document.write( longestSequence(n, arr));// This code is contributed by itsok.</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
