# Longest Increasing Subsequence using Dynamic programming (DP)

Here, we are going to learn how to **find the longest increasing subsequence using dynamic programming (DP)**?

Submitted by Ritik Aggarwal, on November 13, 2018

**Problem:** You are given an array of length **N**. You have to find the **longest increasing subsequence**.

**Constraints:** 1 <= N <= 10^4

Sample inputs: 6 10 1 3 8 81 67 Sample output: 4

**Explanation of the problem:**

We have to find the length of longest increasing subsequence. In sample input the **longest increasing subsequence** is **1,3,8,67** so **length of this is 4**.

**Solution:**

Before going to the code we can see that recursive solution will show time limit exceeded. As recursive solution has time complexity as **O(2^(N))**. So we definitely have to use DP. I will be using a 1D- array in which **i ^{th}** cell represents the

**length of longest increasing subsequence**up to

**i**index in the original array.

^{th}So now is the code of above approach:

#include <iostream> using namespace std; int LIS(int arr[], int n){ int dp[n] = {0}; dp[0] = 1; for (int col = 1; col < n; col++) { int max = 0; for (int i = 0; i < col; i++) { if (arr[i] < arr[col]) { if (max < dp[i]) { max = dp[i]; } } } dp[col] = max+1; } int max1 = -1000000; for(int value : dp) { if(max1<value) { max1 = value; } } return max1; } int main() { int n; cin >> n; int arr[n]; for(int i = 0;i<n;i++){ cin >> arr[i]; } cout << LIS(arr, n) << endl; return 0; }

**Output**

6 10 1 3 8 81 67 4

Though I am using a linear array to store the arrays time complexity is **O(N^2)**. It is not necessary that the dimension of the matrix is the time complexity of the program in the dynamic programming approach.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL