In this problem, we have to find the Longest Increasing Consecutive Subsequence in N elements. We can solve this problem efficiently using Dynamic Programming in O(N) time.

Table of contents:

1. Problem Statement: Longest Increasing Consecutive Subsequence
2. Brute Force approach
3. Improved Naive approach
4. Dynamic Programming approach

In summary, the approach are:

Sorting Algorithm	Time complexity	Space complexity
Brute Force approach	O(N * 2N)	O(1)
Improved Naive approach	O(N2)	O(N)
Dynamic Programming approach	O(N)	O(N)

Let us get started.

Problem Statement: Longest Increasing Consecutive Subsequence

Given an array of size n, write a program that returns the length of the longest increasing subsequence (adjacent element difference is one).

Example

Let the array A = {2 11 3 12 4 5 6 7} of length 8

here we have consecutive increasing sequences (difference between consecutive elements as 1) as:

• Length 6
  • [2, 3, 4, 5, 6, 7]
• Length 5
  • [2, 3, 4, 5, 6]
  • [3, 4, 5, 6, 7]
• Length 4
  • [2, 3, 4, 5]
  • [3, 4, 5, 6]
  • [4, 5, 6, 7]
• Length 3
  • [2, 3, 4]
  • [3, 4, 5]
  • [4, 5, 6]
  • [5, 6, 7]
• Length 2
  • [11, 12]
  • [2, 3]
  • [3, 4]
  • [4, 5]
  • [5, 6]
  • [6, 7]
• Length 1
  • [2]
  • [3]
  • [4]
  • [5]
  • [6]
  • [7]

From these consecutive increasing sequences we have to return length of largest sequence which is:

[2, 3, 4, 5, 6, 7]

Therefore length of largest sequence is 6

Brute Force approach

The steps of Brute Force approach are:

• Generate all subsequences.
• For each subsequence, check if elements are in consecutive order.
• If subsequence is in consecutive order, keep track of the length of the subsequence.
• The largest length is our answer.

Subsequence can be generated by getting the bitwise representation of numbers from 0 to 2^N+1 - 1 for N elements.

As there are 2^N subsequences and to check the conditions, we need O(N) time, the time complexity of Brute Force approach is O(N * 2^N).

The space complexity is O(1).

Improved Naive approach

In this method:

• Step 1: first we will create a loop to select an element
• Step 2: Inside the above loop, we will create another loop which will traverse from the next element of the current element to find a consecutive element.
• Step 3: Store the length of max subsequence in variable.

Pseudo code

• given array list A
• declare variable M for storing max length
• for i element in A
  • traverse list starting from i and check elements which are consecutive to i and store length of that sequence
  • if length is greater then store length in M
• print M

Example

• let the array be a={1, 2, 4, 3} of size n
• declare variable mx=1 for storing max length of sub sequence
• for i=0 to i=n-1
  • we will traverse from index i to end and check if sequence of Increasing consecutive subsequence array exists or not of yes then we will compare size of that array with mx and store max value in mx
  • in first iteration starting from index 0 we will find consecutive increasing subsequence {1, 2, 3}
  • in second iteration starting from index 1 we will find consecutive increasing subsequence {2, 3}
  • in third iteration starting from index 2 we will get consecutive increasing subsequence {4}
  • in last iteration starting from index 3 we will get consecutive increasing subsequence {3}
    therefore subarray with max length will be {1, 2, 3} with length 3
• print mx

Code

#include<bits/stdc++.h>
using namespace std;
void solve() {
  int n; cin>>n;
  int a[n], mx=1;
  for(int i=0; i<n; i++) cin>>a[i];
  for(int i=0; i<n-1; i++)
  {
    int temp = a[i], count=1;
    for(int j=i+1; j<n; j++){
      if(a[j]==temp+1)
      {
        temp = a[j];
        count++;
      }
    }
    mx = max(mx, count);
  }
  cout<<mx<<endl;
}
int main()
{
  solve();
  return 0;
}

Input

8
2 11 3 12 4 5 6 7

Output

6

Time Complexity

O(N²) [as we have used nested for loop]

Space Complexity

O(N) [only one container of size n is created]

Dynamic Programming approach

In this approach:
we will create array dp for storing the length of the longest subsequence [for index i in dp dp[i] will be length of subsequence whose largest element is a[i]]

DP Structure:

DP[i] = length of Longest Increasing Consecutive Subsequence 
        with last element is a[i]

Base case:

DP[i] = 1

As for a subsequence of length 1, it is a increasing consecutive subsequence by definition.

Recursive relation:

if(HASH_MAP.find(a[i]-1) != HASH_MAP.end()){
     int position = HASH_MAP[a[i]-1];
     dp[i] = dp[position] + 1;
}
else 
    dp[i]=1; // BASE CASE

Note, we use a hash map to find the previous consecutive element in constant time O(1) and use this position to update the DP[i] array. You can take a bottom up approach.

Answer:

Answer = MAXIMUM (DP[i]) for all i

The answer is the maximum value in DP[] structure as any element can be the last element of Longest Increasing Consecutive Subsequence.

Example
let array be {1, 2, 3}
and dp = {0, 0, 0}
dp[0] = 1 as 1-1 = 0 is not present in array
dp[1] = dp[index] index = pos of (2-1) = 0
dp[1] = dp[0]+1 = 2 (count of previous consecutive increasing sequence + 1 for current element)
therefore dp[2] = dp[1]+1 = 2+1=3

also we will create a hashmap for index elements in the list.

Pseudo Code

• given array list A of size N
• create list DP of size N for storing max length of subsequence
• DP[i] will denote length if consecutive increasing sequence with max element as A[i]
• store zero in each index in array
• create hash table with key as element and value as its index
• create variable mx for storing max length
• for index i in A
  • if A[i]-1 is present in hashmap then store DP[index] in DP[i] where index = value of A[i]-1 in hashmap or location of element A[i]-1 in A
  • else store 1 in DP[i]
  • add A[i] as key and value as index i in hashmap
  • if DP[i] in mx is less then DP[i] (length of subsequence with max element as A[i])
    print mx

Example

• let array a = { 1, 2, 4, 3 } of length n=4
• let dp = { 0, 0, 0, 0} for dp[i] is length of Increasing consecutive subsequence whose max element is a[i]
• integer mx = 1
• define hashmap mp with key as element and value as its index
• define mx=1 for storing results max length of Increasing consecutive subsequence
• for i=0 to i=n-1
  • check if a[i]-1 is present in hashmap or not
  • if yes then get get value of dp[index] where index = mp[a[i]-1]
    and store dp[index]+1 in dp[i] which is length of Increasing consecutive subsequence having max element as a[i]-1 and 1 for current element count
  • else dp[i]=1 count of current element
  • then we will compare dp[i] to mx and store max of them in mx

By following these rules we will bet our matrix in each iteration as

1. 1st iteration dp = {1 0 0 0}, mx=1
2. 2nd iteration dp = {1 2 0 0}, mx=2
3. 3rd iteration dp = {1 2 1 0}, mx=2
4. 4th iteration dp = {1 2 1 3}, mx=3

we will get length of Longest Increasing consecutive subsequence as mx=3

Code

#include<bits/stdc++.h>
using namespace std;

void solve() {
  int n; cin>>n;
  int a[n], dp[n]={0}, mx=1;
  unordered_map<int, int> mm;
  for(int i=0; i<n; i++) cin>>a[i];
  for(int i=0; i<n; i++)
  {
     if(mm.find(a[i]-1) != mm.end()){
         int pos = mm[a[i]-1];
         dp[i]=dp[pos]+1;
     }
     else dp[i]=1;
     mm[a[i]]=i;
     mx = max(mx, dp[i]);
     cout<<endl;
  }
  cout<<mx<<endl;
}

int main()
{
  solve();
  return 0;
}

Input

8
2 11 3 12 4 5 6 7

Output

6

Time Complexity

• O(N) [as we are traversing array once]

Space Complexity

• O(N) [as we are creating few containers of size n]

With this article at OpenGenus, you must have the complete idea of Longest Increasing Consecutive Subsequence.