Sunday, October 12, 2025
HomeData Modelling & AILongest increasing subsequence which forms a subarray in the sorted representation of...

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

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(2N)
Auxiliary Space: O(N)

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

  1. Store the frequency of each element in the given array in a Map.
  2. Store the original array in a temporary array and sort the given array.
  3. 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.
  4. 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.
  5. 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#




// 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>


Output: 

3

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!

RELATED ARTICLES

Most Popular

Dominic
32352 POSTS0 COMMENTS
Milvus
87 POSTS0 COMMENTS
Nango Kala
6720 POSTS0 COMMENTS
Nicole Veronica
11885 POSTS0 COMMENTS
Nokonwaba Nkukhwana
11941 POSTS0 COMMENTS
Shaida Kate Naidoo
6840 POSTS0 COMMENTS
Ted Musemwa
7105 POSTS0 COMMENTS
Thapelo Manthata
6795 POSTS0 COMMENTS
Umr Jansen
6795 POSTS0 COMMENTS