Longest Increasing Subsequence using Dynamic Programming
Due to optimal substructure and overlapping subproblem property, we can also utilise Dynamic programming to solve the problem. Instead of memoization, we can use the nested loop to implement the recursive relation.
The outer loop will run from i = 1 to N and the inner loop will run from j = 0 to i and use the recurrence relation to solve the problem.
Below is the implementation of the above approach:
// Dynamic Programming C++ implementation
// of LIS problem
#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, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
printf("Length of lis is %d\n", lis(arr, n));
return 0;
}
// Dynamic Programming Java implementation
// of LIS problem
import java.lang.*;
class LIS {
// lis() returns the length of the longest
// increasing subsequence in arr[] of size n
static int lis(int arr[], int n)
{
int lis[] = new int[n];
int i, j, max = 0;
// Initialize LIS values for all indexes
for (i = 0; i < n; i++)
lis[i] = 1;
// Compute optimized LIS values in
// bottom up manner
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// Pick maximum of all LIS values
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.length;
// Function call
System.out.println("Length of lis is "
+ lis(arr, n));
}
}
// This code is contributed by Rajat Mishra
# Dynamic programming Python implementation
# of LIS problem
# lis returns length of the longest
# increasing subsequence in arr of size n
def lis(arr):
n = len(arr)
# Declare the list (array) for LIS and
# initialize LIS values for all indexes
lis = [1]*n
# Compute optimized LIS values in bottom up manner
for i in range(1, n):
for j in range(0, i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j]+1
# Initialize maximum to 0 to get
# the maximum of all LIS
maximum = 0
# Pick maximum of all LIS values
for i in range(n):
maximum = max(maximum, lis[i])
return maximum
# Driver program to test above function
if __name__ == '__main__':
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print("Length of lis is", lis(arr))
# This code is contributed by Nikhil Kumar Singh
// Dynamic Programming C# implementation of LIS problem
using System;
class LIS {
// lis() returns the length of the longest increasing
// subsequence in arr[] of size n
static int lis(int[] arr, int n)
{
int[] lis = new int[n];
int i, j, max = 0;
// Initialize LIS values for all indexes
for (i = 0; i < n; i++)
lis[i] = 1;
// Compute optimized LIS values in bottom up manner
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// Pick maximum of all LIS values
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
// Driver code
public static void Main()
{
int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.Length;
// Function call
Console.WriteLine("Length of lis is "
+ lis(arr, n));
}
}
// This code is contributed by Ryuga
<script>
// Dynamic Programming Javascript implementation
// of LIS problem
// lis() returns the length of the longest
// increasing subsequence in arr[] of size n
function lis(arr, n)
{
let lis = Array(n).fill(0);
let i, j, max = 0;
// Initialize LIS values for all indexes
for(i = 0; i < n; i++)
lis[i] = 1;
// Compute optimized LIS values in
// bottom up manner
for(i = 1; i < n; i++)
for(j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// Pick maximum of all LIS values
for(i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
// Driver code
let arr = [ 10, 22, 9, 33, 21, 50, 41, 60 ];
let n = arr.length;
document.write("Length of lis is " + lis(arr, n) + "\n");
// This code is contributed by avijitmondal1998
</script>
Output
Length of lis is 5
Time Complexity: O(N2) As a nested loop is used.
Auxiliary Space: O(N) Use of any array to store LIS values at each index.
Note: The time complexity of the above Dynamic Programming (DP) solution is O(n^2), but there is an O(N* logN) solution for the LIS problem. We have not discussed the O(N log N) solution here.
Refer: Longest Increasing Subsequence Size (N * logN) for the mentioned approach.
Longest Increasing Subsequence (LIS)
Given an array arr[] of size N, the task is to find the length of the Longest Increasing Subsequence (LIS) i.e., the longest possible subsequence in which the elements of the subsequence are sorted in increasing order.
Longest Increasing Subsequence
Examples:
Input: arr[] = {3, 10, 2, 1, 20}
Output: 3
Explanation: The longest increasing subsequence is 3, 10, 20Input: arr[] = {50, 3, 10, 7, 40, 80}
Output: 4
Explanation: The longest increasing subsequence is {3, 7, 40, 80}Input: arr[] = {30, 20, 10}
Output:1
Explanation: The longest increasing subsequences are {30}, {20} and (10)Input: arr[] = {10, 20, 35, 80}
Output: 4
Explanation: The whole array is sorted
Contact Us