Longest increasing subsequence which forms a subarray in the sorted representation of the array

Last Updated : 12 Dec, 2021

Given an array arr[] of N integers, the task is to find the length of the longest increasing subsequence such that it forms a subarray when the original array is sorted.

Examples:

Input: arr[] = { 2, 6, 4, 8, 2, 9 }
Output: 3
Explanation:
Sorted array: {2, 2, 4, 6, 8, 9}
All possible non-decreasing sequences of the original array are
{2}, {6}, {4}, {8}, {2}, {9}, {2, 2}, {6, 8}, {8, 9}, {6, 8, 9}.
Out of all the above subsequences, {6, 8, 9} is the longest subsequence which is a subarray in the sorted representation of the array.

Input: arr[] = { 5, 5, 6, 6, 5, 5, 5, 6, 5, 5 }
Output: 7
Explanation:
Sorted array: {5, 5, 5, 5, 5, 5, 5, 6, 6, 6}
{5, 5, 5, 5, 5, 5, 5} is the longest subsequence which forms a subarray in the sorted form of the array.

Naive Approach: The idea is to generate all the possible subsequences of the array and then to check which one of them forms the longest subarray when the original array is sorted.

Time Complexity: O(2^N)
Auxiliary Space: O(N)

Efficient Approach: The idea is to use Dynamic Programming approach to solve this problem. Below are the steps:

Store the frequency of each element in the given array in a Map.
Store the original array in a temporary array and sort the given array.
Initialise a 2D array of size N*3 where:
- dp[N][i] will store count of numbers X till position i.
- dp[x][1] will store count of number X + count of numbers (X - 1) till position i.
- dp[x][2] will store the actual length of sequence till position i.
Iterate over the original array and for each index i in the original array, include the element at the current position i only when all the (X – 1) elements are already included in the subsequence and update the values in dp[][] and update the maximum subsequence size after this state.
Print the maximum subsequence size after completing the above steps.

Below is the implementation of the above approach:

C++

// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of the // longest increasing sorted sequence int LongestSequence(int a[], int n) {  // Stores the count of all elements  map<int, int> m;  int ar[n + 1], i, j;  // Store the original array  for (i = 1; i <= n; i++) {  ar[i] = a[i - 1];  }  // Sort the array  sort(a, a + n);  int c = 1;  m[a[0]] = c;  for (i = 1; i <= n; i++) {  // If adjacent element  // are not same  if (a[i] != a[i - 1]) {  // Increment count  c++;  m[a[i]] = c;  }  }  // Store frequency of each element  map<int, int> cnt;  // Initialize a DP array  int dp[n + 1][3] = { 0 };  cnt[0] = 0;  // Iterate over the array ar[]  for (i = 1; i <= n; i++) {  ar[i] = m[ar[i]];  cnt[ar[i]]++;  }  // Length of the longest  // increasing sorted sequence  int ans = 0, x;  // Iterate over the array  for (i = 1; i <= n; i++) {  // Current element  x = ar[i];  // If the element has been  // encountered the first time  if (dp[x][0] == 0) {  // If all the x - 1 previous  // elements have already appeared  if (dp[x - 1][0] == cnt[x - 1]) {  dp[x][1] = dp[x - 1][1];  dp[x][2] = dp[x - 1][1];  }  // Otherwise  else {  dp[x][1] = dp[x - 1][0];  }  }  dp[x][2] = max(dp[x - 1][0],  dp[x][2]);  if (dp[x - 1][0] == cnt[x - 1]) {  // If all x-1 elements have  // already been encountered  dp[x][2] = max(dp[x][2],  dp[x - 1][1]);  }  for (j = 0; j < 3; j++) {  // Increment the count of  // the current element  dp[x][j]++;  // Update maximum  // subsequence size  ans = max(ans, dp[x][j]);  }  }  // Return the maximum  // subsequence size  return ans; } // Driver Code int main() {  int arr[] = { 2, 6, 4, 8, 2, 9 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function Call  cout << LongestSequence(arr, N);  return 0; }

Java

// Java program to implement  // the above approach  import java.io.*; import java.util.*; class GFG{   // Function to find the length of the  // longest increasing sorted sequence  static int LongestSequence(int a[], int n)  {     // Stores the count of all elements   HashMap<Integer, Integer> m = new HashMap<>();    int ar[] = new int[n + 1];  int i = 0;  int j = 0;  // Store the original array   for(i = 1; i <= n; i++)  {   ar[i] = a[i - 1];   }   // Sort the array   Arrays.sort(a);    int c = 1;   m.put(a[0], c);  for(i = 1; i < n; i++)  {     // If adjacent element   // are not same   if (a[i] != a[i - 1])  {     // Increment count   c++;   m.put(a[i], c);  }   }   // Store frequency of each element   HashMap<Integer, Integer> cnt = new HashMap<>();    // Initialize a DP array   int dp[][] = new int[n + 1][3];  cnt.put(0, 0);  // Iterate over the array ar[]   for(i = 1; i <= n; i++)  {   ar[i] = m.get(ar[i]);     if (cnt.containsKey(ar[i]))  cnt.put(ar[i], cnt.get(ar[i]) + 1);  else  cnt.put(ar[i], 1);  }   // Length of the longest   // increasing sorted sequence   int ans = 0, x;   // Iterate over the array   for(i = 1; i <= n; i++)  {     // Current element   x = ar[i];   // If the element has been   // encountered the first time   if (dp[x][0] == 0)  {     // If all the x - 1 previous   // elements have already appeared   if (dp[x - 1][0] == cnt.get(x - 1))  {   dp[x][1] = dp[x - 1][1];   dp[x][2] = dp[x - 1][1];   }   // Otherwise   else   {   dp[x][1] = dp[x - 1][0];   }   }     dp[x][2] = Math.max(dp[x - 1][0],   dp[x][2]);   if (dp[x - 1][0] == cnt.get(x - 1))  {     // If all x-1 elements have   // already been encountered   dp[x][2] = Math.max(dp[x][2],   dp[x - 1][1]);   }   for(j = 0; j < 3; j++)  {   // Increment the count of   // the current element   dp[x][j]++;   // Update maximum   // subsequence size   ans = Math.max(ans, dp[x][j]);   }   }     // Return the maximum   // subsequence size   return ans;  }  // Driver code public static void main(String[] args) {  int arr[] = { 2, 6, 4, 8, 2, 9 };   int n = arr.length;    System.out.println(LongestSequence(arr, n)); } } // This code is contributed by bikram2001jha

Python3

# Python 3 program to implement # the above approach # Function to find the length of the # longest increasing sorted sequence def LongestSequence(a, n): # Stores the count of all elements m = {i : 0 for i in range(100)} ar = [0 for i in range(n + 1)] # Store the original array for i in range(1, n + 1): ar[i] = a[i - 1] # Sort the array a.sort(reverse = False) c = 1 m[a[0]] = c for i in range(1, n): # If adjacent element # are not same if (a[i] != a[i - 1]): # Increment count c += 1 m[a[i]] = c # Store frequency of each element cnt = {i : 0 for i in range(100)} # Initialize a DP array dp = [[0 for i in range(3)] for j in range(n + 1)] cnt[0] = 0 # Iterate over the array ar[] for i in range(1, n + 1): ar[i] = m[ar[i]] cnt[ar[i]] += 1 # Length of the longest # increasing sorted sequence ans = 0 # Iterate over the array for i in range(1, n + 1): # Current element x = ar[i] # If the element has been # encountered the first time if (dp[x][0] == 0): # If all the x - 1 previous # elements have already appeared if (dp[x - 1][0] == cnt[x - 1]): dp[x][1] = dp[x - 1][1] dp[x][2] = dp[x - 1][1] # Otherwise else: dp[x][1] = dp[x - 1][0] dp[x][2] = max(dp[x - 1][0], dp[x][2]) if (dp[x - 1][0] == cnt[x - 1]): # If all x-1 elements have # already been encountered dp[x][2] = max(dp[x][2], dp[x - 1][1]) for j in range(3): # Increment the count of # the current element dp[x][j] += 1 # Update maximum # subsequence size ans = max(ans, dp[x][j]) # Return the maximum # subsequence size return ans # Driver Code if __name__ == '__main__': arr = [ 2, 6, 4, 8, 2, 9 ] N = len(arr) # Function call print(LongestSequence(arr, N)) # This code is contributed by SURENDRA_GANGWAR

// C# program to implement  // the above approach  using System.Collections.Generic;  using System;  class GFG{    // Function to find the length of the  // longest increasing sorted sequence  static int LongestSequence(int []a, int n)  {     // Stores the count of all elements   Dictionary<int,   int> m = new Dictionary<int,  int>();    int []ar = new int[n + 1];   int i = 0;   int j = 0;   // Store the original array   for(i = 1; i <= n; i++)   {   ar[i] = a[i - 1];   }   // Sort the array   Array.Sort(a);     int c = 1;   m[a[0]]= c;   for(i = 1; i < n; i++)   {     // If adjacent element   // are not same   if (a[i] != a[i - 1])   {     // Increment count   c++;   m[a[i]]= c;   }   }   // Store frequency of each element   Dictionary<int,   int>cnt = new Dictionary<int,   int>();    // Initialize a DP array   int [,]dp = new int[n + 1, 3];   cnt[0] = 0;   // Iterate over the array ar[]   for(i = 1; i <= n; i++)   {   ar[i] = m[ar[i]];     if (cnt.ContainsKey(ar[i]))   cnt[ar[i]]= cnt[ar[i]] + 1;   else  cnt[ar[i]]= 1;   }   // Length of the longest   // increasing sorted sequence   int ans = 0, x;   // Iterate over the array   for(i = 1; i <= n; i++)   {     // Current element   x = ar[i];   // If the element has been   // encountered the first time   if (dp[x, 0] == 0)   {     // If all the x - 1 previous   // elements have already appeared   if (dp[x - 1, 0] == cnt[x - 1])   {   dp[x, 1] = dp[x - 1, 1];   dp[x, 2] = dp[x - 1, 1];   }   // Otherwise   else  {   dp[x, 1] = dp[x - 1, 0];   }   }     dp[x, 2] = Math.Max(dp[x - 1, 0],   dp[x, 2]);   if (dp[x - 1, 0] == cnt[x - 1])   {     // If all x-1 elements have   // already been encountered   dp[x, 2] = Math.Max(dp[x, 2],   dp[x - 1, 1]);   }   for(j = 0; j < 3; j++)   {   // Increment the count of   // the current element   dp[x, j]++;   // Update maximum   // subsequence size   ans = Math.Max(ans, dp[x, j]);   }   }     // Return the maximum   // subsequence size   return ans;  }  // Driver code  public static void Main()  {   int []arr = { 2, 6, 4, 8, 2, 9 };   int n = arr.Length;     Console.WriteLine(LongestSequence(arr, n));  }  }  // This code is contributed by Stream_Cipher

JavaScript

<script> // JavaScript program to implement // the above approach // Function to find the length of the // longest increasing sorted sequence function LongestSequence(a, n) {  // Stores the count of all elements  var m = new Map();  var ar = Array(n+1).fill(0), i, j;  // Store the original array  for (i = 1; i <= n; i++) {  ar[i] = a[i - 1];  }  // Sort the array  a.sort((a,b)=>a-b);  var c = 1;  m.set(a[0], c);  for (i = 1; i <= n; i++) {  // If adjacent element  // are not same  if (a[i] != a[i - 1]) {  // Increment count  c++;  m.set(a[i], c);  }  }  // Store frequency of each element  var cnt = new Map();  // Initialize a DP array  var dp = Array.from(Array(n+1), ()=>Array(3).fill(0));  cnt.set(0, 0);  // Iterate over the array ar[]  for (i = 1; i <= n; i++) {  ar[i] = m.get(ar[i]);  if(cnt.has(ar[i]))  cnt.set(ar[i], cnt.get(ar[i])+1)  else  cnt.set(ar[i], 1)  }  // Length of the longest  // increasing sorted sequence  var ans = 0, x;  // Iterate over the array  for (i = 1; i <= n; i++) {  // Current element  x = ar[i];  // If the element has been  // encountered the first time  if (dp[x][0] == 0) {  // If all the x - 1 previous  // elements have already appeared  if (dp[x - 1][0] == cnt.get(x - 1)) {  dp[x][1] = dp[x - 1][1];  dp[x][2] = dp[x - 1][1];  }  // Otherwise  else {  dp[x][1] = dp[x - 1][0];  }  }  dp[x][2] = Math.max(dp[x - 1][0],  dp[x][2]);  if (dp[x - 1][0] == cnt[x - 1]) {  // If all x-1 elements have  // already been encountered  dp[x][2] = Math.max(dp[x][2],  dp[x - 1][1]);  }  for (j = 0; j < 3; j++) {  // Increment the count of  // the current element  dp[x][j]++;  // Update maximum  // subsequence size  ans = Math.max(ans, dp[x][j]);  }  }  // Return the maximum  // subsequence size  return ans; } // Driver Code var arr = [2, 6, 4, 8, 2, 9]; var N = arr.length; // Function Call document.write( LongestSequence(arr, N)); </script>