What other approach can be used to find the longest increasing subsequence?

The approach other than this is by using Dynamic Programming in O(n^2) time.

Table of contents

Introduction

Problem Statement

Approach

Code

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

Longest Increasing Subsequence Size

Author Deleted User

Introduction

What do you understand by this term ‘Subsequence.’? A subsequence is the sequence of an element from a given sequence such that the sequence is contiguous or non-contiguous. It will be more evident when we will start with an example. To solve this problem in O(n logn), we will be using two significant hubs of competitive programming, i.e., Binary Search and Dynamic Programming.

Binary search is a searching algorithm that follows the divide and conquer approach to search an element in a sorted array of elements in O(logn) time.

Dynamic programming is used to have problems, divided into similar sub-problems to re-use their results. Primarily, these algorithms are used for optimization.

Problem Statement

We will be given a sequence of n numbers, and we have to find the length of the longest increasing subsequence.

Suppose you are given a sequence of n=5 elements.

Here the longest increasing subsequence is:

I.e length = 3

Let us understand the problem with one more example in detail.

Assume we are given a sequence that has [2,5,3,7,11,8,10,13,6]; let’s see how our algorithm works for this subsequence.

Initially, at the ‘0th’ index, you store ‘2’ and come across as ‘5’. Now you will check that if 5>2, it is so that you will insert ‘5’ at index ‘1’.

Now we come across the next element, i.e., ‘3.’ Now, this ‘3’ is not greater than ‘5’, so you will traverse and find who is the immediate next of ‘3’ or ‘3’ exists in this array no it doesn’t exist. So the immediate next element is ‘5’ and replaces this ‘5’ with ‘3’.

The next element in the array after ‘3’ is ‘7’ and 7>3. So insert 7 in the list at the 2nd position.

The next element in the array after ‘7’ is ‘11’ and 11>7, So insert 11 in the list at the 3rd position.

Now we come across the next element, i.e., ‘8.’ Now, this ‘8’ is not greater than ‘11’, so you will traverse and find who is the immediate next of ‘8’. So the immediate next element is ‘11’ and replaces this ‘11’ with ‘8’.

The next element in the array after ‘8’ is ‘10’ and 10>8, So insert 10 in the list at the 4th position.

The next element in the array after ‘10’ is ‘13’ and 13>10, So insert 13 in the list at the 5th position.

Now we come across the next element, i.e., ‘6.’ Now, this ‘6’ is not greater than ‘13’, so you will traverse and find who is the immediate next of ‘6’. So the immediate next element is ‘7’ and replaces this ‘7’ with ‘6’.

The number of elements that we are putting in our list is the length of the longest increasing subsequence.

Why does this has worked?

We store the last element of that possible sequence length; suppose you take the index from 0 to 2. This means that the subsequence length is ‘3’ and at every index here takes the minimum element.

Approach

To find the next immediate element, which will always be in increasing order, discover that we could do a binary search over here that will take log(n) time, and the entire traversal of the array will take O(n) time. Assuming that we have applied binary search for every element.

Code

import java.io.*;
import java.util.*;
import java.lang.Math;

class Solution {
// Binary Search
static int increasing(int arr[], int low, int high, int key)
{
while (high - low > 1) {
int m = low + (high - low) / 2;
if (arr[m] >= key)
high = m;
else
low = m;
}

return high;
}

static int Increasing_Length(int arr[], int n)
{
// Add boundary case, when the array size is one

int[] res = new int[n];
int len; 

res[0] = arr[0];
len = 1;
for (int i = 1; i < n; i++) {
if (arr[i] < res[0])

res[0] = arr[i];

else if (arr[i] > res[len - 1])
// To find the increasing subsequence
res[len++] = arr[i];

else

res[increasing(res, -1, len - 1, arr[i])] = arr[i];
}

return len;
}

// Main Function
public static void main(String[] args)
{
int arr[] = {2,5,3,7,11,8,10,13,6 };
int n = arr.length;
System.out.println(Increasing_Length(arr,n));
}
}

You can also try this code with Online Java Compiler

Run Code

Output

You can also try this code with Online Java Compiler

Run Code

Check out Longest Common Substring

Refer to know about : Longest common subsequence

FAQs

What other approach can be used to find the longest increasing subsequence?
The approach other than this is by using Dynamic Programming in O(n^2) time.
What do you mean by a subsequence?
A subsequence is the sequence of an element from a given sequence such that the sequence is contiguous or non-contiguous.

Key Takeaways

This blog has covered the most asked problem in companies like Paytm, Samsung, etc. The Longest increasing subsequence size is solved using O(n logn) time in the Java language, where we have to find the length of the longest subsequence using binary search.

Another approach to solving the problem is using a dynamic programming algorithm in O(n^2) time complexity.

You can visit these articles to elaborate on Binary Search and Dynamic Programming.

You can use Coding Ninjas Studio for various DSA questions typically asked in interviews for more practice. It will help you in mastering efficient coding techniques.