Longest Increasing Subsequence
Definition
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
How it Works
For every element arr[i], we want to find the longest chain ending at i.
- Look at all previous elements (j < i).
- If arr[i] is bigger than arr[j], we can extend the chain ending at j.
- LIS[i] = 1 + max(LIS[j]) for all valid j.
Example
Input: [10, 22, 9, 33, 21, 50, 41, 60] LIS: 10, 22, 33, 50, 60 Length: 5
Code Example
PythonJavaCC++
# Longest Increasing Subsequence (DP)
def lis(arr):
n = len(arr)
# Initialize dp array
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j] and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
return max(dp)
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print("Length of LIS is", lis(arr)) # 5
public class LIS_DP {
public static int lis(int[] arr) {
int n = arr.length;
int[] dp = new int[n];
for (int i = 0; i < n; i++)
dp[i] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j arr[j] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
int max = dp[0];
for (int i = 1; i max)
max = dp[i];
return max;
}
public static void main(String[] args) {
int[] arr = {10,22,9,33,21,50,41,60};
System.out.println("Length of LIS is " + lis(arr));
}
}
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lis(int arr[], int n) {
int dp[n];
for (int i = 0; i < n; i++)
dp[i] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j arr[j] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
int maximum = dp[0];
for (int i = 1; i < n; i++)
maximum = max(maximum, dp[i]);
return maximum;
}
int main() {
int arr[] = {10,22,9,33,21,50,41,60};
int n = 8;
printf("Length of LIS is %d\n", lis(arr, n));
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int lis(vector<int> arr) {
int n = arr.size();
vector<int> dp(n,1);
for (int i = 1; i < n; i++) {
for (int j = 0; j arr[j] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
int maximum = dp[0];
for (int i = 1; i < n; i++)
maximum = max(maximum, dp[i]);
return maximum;
}
int main() {
vector<int> arr = {10,22,9,33,21,50,41,60};
cout << "Length of LIS is "
<< lis(arr);
return 0;
}
Complexity Analysis
- Time Complexity: O(N^2) (Nested loops). Note: Can be optimized to O(N log N) using Binary Search.
- Space Complexity: O(N).