Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47
A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

In dynamic programming, a problem may be broken down into smaller subproblems and solved more efficiently, since the optimum solution to the core problem is dependent on the optimal solution to each of the smaller subproblems. Richard Bellman came up with the idea for the method back in the '50s. The DP method only computes the answer to each subproblem once and then remembers it, saving time by not recomputing it for subsequent appearances of the same subproblem.

By the end of this tutorial, you will better understand the recursive and dynamic programming approach to find the Longest Increasing Subsequence with the necessary details and practical implementations.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

Problem Statement for the Longest Increasing Subsequence Problem

The Longest increasing subsequence (LIS) problem involves finding the length of the longest increasing subsequence inside a given sequence. All items within it are sorted in ascending order of increasing length. As an example, the length of LIS for the set {10, 15, 13, 9, 21, 22, 35, 29, 64} is 6 and LIS is the set {10, 15, 21, 22, 35, 64}.

Now, look at the recursive solution to solve the Longest increasing subsequence.

Recursion-Based Solution to Find the Longest Increasing Subsequence

longest_Increasing_Subsequence-Recursion-img1

This recursive approach is more of a brute force approach. You will follow the below steps to find LIS length:

  1. You will search for an increasing subsequence for every element and then pick the one with the maximum length.
  2. You will start with fixing the ending point first and then go from there.
  3. You will decrease the indices and look for the second last element, and so on.
  4. Finally, you will select the subsequence with the highest length and declare it as LIS.

And this is how you find the Longest increasing subsequence using recursion. Now, implement this solution through a simple C++ code.

Implement the Recursion-Based Solution to Find the Longest Increasing Subsequence

You will be provided with a set with elements {10, 15, 13, 9, 21, 22, 35, 29, 64}. Now, you are to find the longest increasing subsequence in this set, which will come out to be the LIS{10, 13, 21, 22, 29, 64} and of length equal to six.

Code:

/* A C++ program to implement recursive solution

of LIS problem */

#include <bits/stdc++.h>

using namespace std;

/* To make use of recursive calls, this

the function will return two things:

1) We use curmaxending to get Length of LIS ending with element arr[n-1]

2) Overall maximum as the LIS may end with

an element before arr[N-1]. maxref is

used this purpose.

The value of LIS of a full array of size n

is stored in *max_ref, which is our final result

*/

int _lis(int arr[], int N, int* maxref)

{

/* Base case */

if (N == 1)

return 1;

// 'curmaxending' is length of LIS

// ending with arr[N-1]

int res, curmaxending = 1;

/* Recursively get all LIS ending with arr[0],

arr[1] ... arr[n-2]. If arr[i-1] is smaller

than arr[N-1], and max ending with arr[N-1]

needs to be updated, then update it */

for (int i = 1; i < N; i++) {

res = _lis(arr, i, maxref);

if (arr[i - 1] < arr[N - 1]

&& res + 1 > curmaxending)

curmaxending = res + 1;

}

// Compare curmaxending with the overall

// max. And update the overall max if needed

if (*maxref < curmaxending)

*maxref = curmaxending;

// Return length of LIS ending with arr[N-1]

return curmaxending;

}

// The wrapper function for _lis()

int lis(int arr[], int N)

{

// The max variable holds the result

int max = 1;

// The function _lis() stores its result in max

_lis(arr, N, &max);

// returns max

return max;

}

int main()

{

int arr[] = { 10, 15, 13, 9, 21, 22, 35, 29, 64 };

int N = sizeof(arr) / sizeof(arr[0]);

cout <<"Length of lis is "<< lis(arr, N);

return 0;

}

longest_Increasing_Subsequence-Recursion-implementation-img1.

You have now discussed the recursive approach to find the Longest increasing subsequence with a code. This method has a time complexity of O(2n). If you look at the recursion tree of the above method, you will find some overlapping subproblems. That means you can still improve your time complexity. Now, see the dynamic programming-based solution to this problem.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Dynamic Programming Based Solution to Find the Longest Increasing Subsequence

longest_Increasing_Subsequence-DP-img1

Since the recursive approach uses a top-down approach, you will follow the bottom-up approach.

  • First, make a 1D array of size n.
  • Next, you must iterate it for each element from index 1 to n-1.
  • You will iterate the elements with indices smaller than the current element in a nested loop for each element.
  • In this nested loop, if you find the element’s value is lesser than the current element, then you will assign lis[i] with (lis[j]+1) and if (lis[j]+1) is greater than lis[i].
  • Finally, you will traverse the entire lis[] array to find the maximum element, which will conclude your answer.

And this is how you solve this problem using dynamic programming. Now implement this solution through a simple C++ code.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Implement the Dynamic Programming Based Solution to Find the Longest Increasing Subsequence

You will be provided with a set with elements {10, 15, 13, 9, 21, 22, 35, 29, 64}. You are to find the longest increasing subsequence in this set, which will come out to be the LIS{10, 15, 21, 22, 35, 64} and of length equal to six.

Code: 

//A C++ program to implement LIS problem using Dynamic Programming  

#include <bits/stdc++.h>

using namespace std;

/* lis() returns the length of the longest

increasing subsequence in arr[] of size N */

int lis(int arr[], int N)

{

int lis[N];

lis[0] = 1;

/* Compute optimized LIS values in

bottom up manner */

for (int i = 1; i < N; i++) {

lis[i] = 1;

for (int j = 0; j < i; j++)

if (arr[i] > arr[j] && lis[i] < lis[j] + 1)

lis[i] = lis[j] + 1;

}

// Return maximum value in lis[]

return *max_element(lis, lis + N);

}

/* Driver program to test above function */

int main()

{

int arr[] = { 10, 15, 13, 9, 21, 22, 35, 29, 64 };

int N = sizeof(arr) / sizeof(arr[0]);

printf("Length of longest increasing sub-sequence is %d\n", lis(arr, N));

return 0;

}

longest_Increasing_Subsequence-DP-implementation-img1.

With this, you have come to an end of this tutorial. You will now look at what could be your next steps to conquer dynamic programming problems.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

Your next stop in mastering dynamic programming problems should be Knapsack Problem. The knapsack problem is used to explain both the problem and the solution. It derives its name from the limited number of things that may be carried in a fixed-size knapsack. You are given a selection of varying weights and values; your objective is to cram as much worth into the knapsack as possible while staying within the weight limit.

If you're searching for a more in-depth understanding of software development that can help you carve out a successful career in the field, look no further. If that's the case, consider Simplilearn's Postgraduate Program in Full Stack Web Development, which is offered in collaboration with Caltech CTME, the world's largest technology education institution. This Post-Graduate Program will teach you how to grasp both front-end and back-end Java technologies, beginning with the basics and moving to more sophisticated Full Stack Web Development subjects. In this web development course, you'll study Angular, Spring Boot, Hibernate, JSPs, and MVC, which will help you get started as a full-stack developer. 

If you have any questions or require clarification on this "Longest Increasing Subsequence" tutorial, please leave them in the comments section below. Our expert team will review them and respond as soon as possible.

About the Author

Vaibhav KhandelwalVaibhav Khandelwal

Vaibhav Khandelwal is a proactive tech geek who's always on the edge of learning new technologies. He is well versed in competitive programming and possess sound knowledge of web development. He likes to read fictional and sci-fi novels and likes to play strategy games like chess.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.