Longest Increasing consecutive subsequence

Last Updated : 08 Oct, 2023

Given N elements, write a program that prints the length of the longest increasing consecutive subsequence.

Examples:

Input : a[] = {3, 10, 3, 11, 4, 5, 6, 7, 8, 12}
Output : 6
Explanation: 3, 4, 5, 6, 7, 8 is the longest increasing subsequence whose adjacent element differs by one.

Input : a[] = {6, 7, 8, 3, 4, 5, 9, 10}
Output : 5
Explanation: 6, 7, 8, 9, 10 is the longest increasing subsequence

Naive Approach: For every element, find the length of the subsequence starting from that particular element. Print the longest length of the subsequence thus formed:

C++

#include <bits/stdc++.h>
using namespace std;
 
int LongestSubsequence(int a[], int n)
{
    int ans = 0;
   
      // Traverse every element to check if any 
    // increasing subsequence starts from this index
    for(int i=0; i<n; i++)
    {
          // Initialize cnt variable as 1, which defines 
        // the current length of the increasing subsequence
        int cnt = 1;
        for(int j=i+1; j<n; j++)
            if(a[j] == (a[i]+cnt)) cnt++;
         
      // Update the answer if the current length is 
      // greater than already found length
        ans = max(ans, cnt);
    }
     
    return ans;
}
 
int main()
{
    int a[] = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << LongestSubsequence(a, n);
 
    return 0;
}

Java

import java.util.Scanner;
 
public class Main {
 
  public static int LongestSubsequence(int a[], int n)
  {
 
    int ans = 0;
   
      // Traverse every element to check if any 
    // increasing subsequence starts from this index
    for(int i=0; i<n; i++)
    {
          // Initialize cnt variable as 1, which defines 
        // the current length of the increasing subsequence
        int cnt = 1;
        for(int j=i+1; j<n; j++)
            if(a[j] == (a[i]+cnt)) cnt++;
         
      // Update the answer if the current length is 
      // greater than already found length
        if(cnt > ans)
          ans = cnt;
    }
     
    return ans;
  }
  public static void main(String[] args) {
    int[] a = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12};
    int n = a.length;
    System.out.println(LongestSubsequence(a, n));
  }
}
 
// This code contributed by Ajax

Python3

def longest_subsequence(a, n):
    ans = 0
 
    # Traverse every element to check if any
    # increasing subsequence starts from this index
    for i in range(n):
        # Initialize cnt variable as 1, which defines
        # the current length of the increasing subsequence
        cnt = 1
        for j in range(i + 1, n):
            if a[j] == (a[i] + cnt):
                cnt += 1
 
        # Update the answer if the current length is
        # greater than the already found length
        ans = max(ans, cnt)
 
    return ans
 
if __name__ == "__main__":
    a = [3, 10, 3, 11, 4, 5, 6, 7, 8, 12]
    n = len(a)
    print(longest_subsequence(a, n))

C#

using System;
 
class GFG
{
    static int LongestSubsequence(int[] a, int n)
    {
        int ans = 0;
        // Traverse every element to check if any 
        // increasing subsequence starts from this index
        for (int i = 0; i < n; i++)
        {
            // Initialize cnt variable as 1, which defines 
            // current length of the increasing subsequence
            int cnt = 1;
            for (int j = i + 1; j < n; j++)
            {
                if (a[j] == (a[i] + cnt))
                {
                    cnt++;
                }
                // Update the answer if the current length is 
                // greater than the already found length
                ans = Math.Max(ans, cnt);
            }
        }
        return ans;
    }
    static void Main()
    {
        int[] a = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 };
        int n = a.Length;
        Console.WriteLine(LongestSubsequence(a, n));
    }
}

Javascript

function LongestSubsequence(a, n)
{
    let ans = 0;
   
      // Traverse every element to check if any 
    // increasing subsequence starts from this index
    for(let i=0; i<n; i++)
    {
          // Initialize cnt variable as 1, which defines 
        // the current length of the increasing subsequence
        let cnt = 1;
        for(let j=i+1; j<n; j++)
            if(a[j] == (a[i]+cnt)) cnt++;
         
      // Update the answer if the current length is 
      // greater than already found length
        ans = Math.max(ans, cnt);
    }
     
    return ans;
}
 
let a = [ 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 ];
let n = a.length;
console.log(LongestSubsequence(a, n));

Output

Time Complexity: O(N²)
Auxiliary Space: O(1)

Dynamic Programming Approach: Let DP[i] store the length of the longest subsequence which ends with A[i]. For every A[i], if A[i]-1 is present in the array before i-th index, then A[i] will add to the increasing subsequence which has A[i]-1. Hence, DP[i] = DP[ index(A[i]-1) ] + 1. If A[i]-1 is not present in the array before i-th index, then DP[i]=1 since the A[i] element forms a subsequence which starts with A[i]. Hence, the relation for DP[i] is:

If A[i]-1 is present before i-th index:

DP[i] = DP[ index(A[i]-1) ] + 1

else:

DP[i] = 1

Given below is the illustration of the above approach:

C++

// CPP program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
#include <bits/stdc++.h>
using namespace std;
 
// function that returns the length of the
// longest increasing subsequence
// whose adjacent element differ by 1
int longestSubsequence(int a[], int n)
{
    // stores the index of elements
    unordered_map<int, int> mp;
 
    // stores the length of the longest
    // subsequence that ends with a[i]
    int dp[n];
    memset(dp, 0, sizeof(dp));
 
    int maximum = INT_MIN;
 
    // iterate for all element
    for (int i = 0; i < n; i++) {
 
        // if a[i]-1 is present before i-th index
        if (mp.find(a[i] - 1) != mp.end()) {
 
            // last index of a[i]-1
            int lastIndex = mp[a[i] - 1] - 1;
 
            // relation
            dp[i] = 1 + dp[lastIndex];
        }
        else
            dp[i] = 1;
 
        // stores the index as 1-index as we need to
        // check for occurrence, hence 0-th index
        // will not be possible to check
        mp[a[i]] = i + 1;
 
        // stores the longest length
        maximum = max(maximum, dp[i]);
    }
 
    return maximum;
}
 
// Driver Code
int main()
{
    int a[] = { 4, 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << longestSubsequence(a, n);
    return 0;
}

Java

// Java program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
 
import java.util.*;
class lics {
    static int LongIncrConseqSubseq(int arr[], int n)
    {
        // create hashmap to save latest consequent 
        // number as "key" and its length as "value"
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // put first element as "key" and its length as "value"
        map.put(arr[0], 1);
        for (int i = 1; i < n; i++) {
        
            // check if last consequent of arr[i] exist or not
            if (map.containsKey(arr[i] - 1)) {
        
                // put the updated consequent number 
                // and increment its value(length)
                map.put(arr[i], map.get(arr[i] - 1) + 1);
           
                // remove the last consequent number
                map.remove(arr[i] - 1);
            }
 
            // if there is no last consequent of
            // arr[i] then put arr[i]
            else {
                map.put(arr[i], 1);
            }
        }
        return Collections.max(map.values());
    }
 
    // driver code
    public static void main(String args[])
    {
        // Take input from user
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        System.out.println(LongIncrConseqSubseq(arr, n));
    }
}
// This code is contributed by CrappyDoctor

Python3

# python program to find length of the 
# longest increasing subsequence 
# whose adjacent element differ by 1 
 
from collections import defaultdict
import sys
 
# function that returns the length of the 
# longest increasing subsequence 
# whose adjacent element differ by 1 
 
def longestSubsequence(a, n):
    mp = defaultdict(lambda:0)
 
    # stores the length of the longest 
    # subsequence that ends with a[i] 
    dp = [0 for i in range(n)]
    maximum = -sys.maxsize
 
    # iterate for all element 
    for i in range(n):
 
        # if a[i]-1 is present before i-th index 
        if a[i] - 1 in mp:
 
            # last index of a[i]-1 
            lastIndex = mp[a[i] - 1] - 1
 
            # relation 
            dp[i] = 1 + dp[lastIndex]
        else:
            dp[i] = 1
 
            # stores the index as 1-index as we need to 
            # check for occurrence, hence 0-th index 
            # will not be possible to check 
        mp[a[i]] = i + 1
 
        # stores the longest length 
        maximum = max(maximum, dp[i])
    return maximum
 
 
# Driver Code 
a = [3, 10, 3, 11, 4, 5, 6, 7, 8, 12]
n = len(a)
print(longestSubsequence(a, n))
 
# This code is contributed by Shrikant13

C#

// C# program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
using System;
using System.Collections.Generic;
class GFG{
     
static int longIncrConseqSubseq(int []arr, 
                                int n)
{
  // Create hashmap to save 
  // latest consequent number 
  // as "key" and its length 
  // as "value"
  Dictionary<int, 
             int> map = new Dictionary<int, 
                                       int>();
 
  // Put first element as "key" 
  // and its length as "value"
  map.Add(arr[0], 1);
  for (int i = 1; i < n; i++) 
  {
    // Check if last consequent 
    // of arr[i] exist or not
    if (map.ContainsKey(arr[i] - 1)) 
    {
      // put the updated consequent number 
      // and increment its value(length)
      map.Add(arr[i], map[arr[i] - 1] + 1);
 
      // Remove the last consequent number
      map.Remove(arr[i] - 1);
    }
 
    // If there is no last consequent of
    // arr[i] then put arr[i]
    else
    {
      if(!map.ContainsKey(arr[i]))
        map.Add(arr[i], 1);
    }
  }
   
  int max = int.MinValue;
  foreach(KeyValuePair<int, 
                       int> entry in map)
  {
    if(entry.Value > max)
    {
      max = entry.Value;
    }
  }
  return max;
}
 
// Driver code
public static void Main(String []args)
{
  // Take input from user
  int []arr = {3, 10, 3, 11, 
               4, 5, 6, 7, 8, 12};
  int n = arr.Length;
  Console.WriteLine(longIncrConseqSubseq(arr, n));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
 
// function that returns the length of the
// longest increasing subsequence
// whose adjacent element differ by 1
function longestSubsequence(a, n)
{
    // stores the index of elements
    var mp = new Map();
 
    // stores the length of the longest
    // subsequence that ends with a[i]
    var dp = Array(n).fill(0);
 
    var maximum = -1000000000;
 
    // iterate for all element
    for (var i = 0; i < n; i++) {
 
        // if a[i]-1 is present before i-th index
        if (mp.has(a[i] - 1)) {
 
            // last index of a[i]-1
            var lastIndex = mp.get(a[i] - 1) - 1;
 
            // relation
            dp[i] = 1 + dp[lastIndex];
        }
        else
            dp[i] = 1;
 
        // stores the index as 1-index as we need to
        // check for occurrence, hence 0-th index
        // will not be possible to check
        mp.set(a[i], i + 1);
 
        // stores the longest length
        maximum = Math.max(maximum, dp[i]);
    }
 
    return maximum;
}
 
// Driver Code
var a = [3, 10, 3, 11, 4, 5, 6, 7, 8, 12];
var n = a.length;
document.write( longestSubsequence(a, n));
 
</script>

Output

Complexity Analysis:

Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for dp and map m.

Striver

Improve

Find the length of largest subarray with 0 sum

Count distinct elements in every window of size k

Easy problems on Hashing

Intermediate problems on Hashing

Hard problems on Hashing

Longest Increasing consecutive subsequence

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?