Longest Increasing Subsequence
In this page:
LIS Idea
The longest increasing subsequence of an array is the longest run of elements, not necessarily adjacent, that keeps strictly increasing in value as you read left to right through the original array.
Example: LIS Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {3,1,4,1,5,9,2,6};
cout << "Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4";
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {3,1,4,1,5,9,2,6};
System.out.println("Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4");
}
}arr = [3,1,4,1,5,9,2,6]
print("Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4")#include <stdio.h>
int main() {
int arr[] = {3,1,4,1,5,9,2,6};
printf("Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4");
return 0;
}Login to try C/C++/Java code in the editor
DP State
dp[i] stores the length of the longest increasing subsequence that ends exactly at index i, so the overall answer is simply the largest value found anywhere in the dp array once it's fully computed.
Example: DP State
#include <iostream>
using namespace std;
int main() {
int arr[] = {3,1,4,1,5,9,2,6};
int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
cout << "dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)";
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {3,1,4,1,5,9,2,6};
int[] dp = new int[8];
java.util.Arrays.fill(dp, 1);
System.out.println("dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)");
}
}arr = [3,1,4,1,5,9,2,6]
dp = [1] * 8
print("dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)")#include <stdio.h>
int main() {
int arr[] = {3,1,4,1,5,9,2,6};
int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
printf("dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)");
return 0;
}Login to try C/C++/Java code in the editor
Transition
For each index i, you look back at every earlier index j: if the value at j is smaller than the value at i, index i could extend that subsequence, so dp[i] becomes the largest dp[j] + 1 among all such valid j.
Example: Transition
#include <iostream>
using namespace std;
int main() {
int arr[] = {3,1,4,1,5,9,2,6};
int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
int best = 1;
for (int i = 1; i < 8; i++) {
for (int j = 0; j < i; j++)
if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j]+1);
best = max(best, dp[i]);
}
cout << "Longest increasing subsequence length: " << best;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {3,1,4,1,5,9,2,6};
int[] dp = new int[8];
java.util.Arrays.fill(dp, 1);
int best = 1;
for (int i = 1; i < 8; i++) {
for (int j = 0; j < i; j++)
if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j]+1);
best = Math.max(best, dp[i]);
}
System.out.println("Longest increasing subsequence length: " + best);
}
}arr = [3,1,4,1,5,9,2,6]
dp = [1]*8
best = 1
for i in range(1, 8):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j]+1)
best = max(best, dp[i])
print("Longest increasing subsequence length:", best)#include <stdio.h>
int main() {
int arr[] = {3,1,4,1,5,9,2,6};
int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
int best = 1;
for (int i = 1; i < 8; i++) {
for (int j = 0; j < i; j++)
if (arr[j] < arr[i] && dp[j]+1 > dp[i]) dp[i] = dp[j]+1;
if (dp[i] > best) best = dp[i];
}
printf("Longest increasing subsequence length: %d", best);
return 0;
}Login to try C/C++/Java code in the editor
Reconstruction
Keeping track of which earlier index each dp[i] extended from lets you walk backward from the best ending index and rebuild the actual sequence of values, not just report how long it is.
Example: Reconstruction
#include <iostream>
using namespace std;
int main() {
int arr[] = {3,1,4,1,5};
int dp[5], from[5];
for (int i=0;i<5;i++) { dp[i]=1; from[i]=-1; }
for (int i = 1; i < 5; i++)
for (int j = 0; j < i; j++)
if (arr[j] < arr[i] && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; from[i]=j; }
cout << "from[] lets you walk backward from the best-ending index to rebuild the actual sequence";
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {3,1,4,1,5};
int[] dp = new int[5], from = new int[5];
java.util.Arrays.fill(dp, 1);
java.util.Arrays.fill(from, -1);
for (int i = 1; i < 5; i++)
for (int j = 0; j < i; j++)
if (arr[j] < arr[i] && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; from[i]=j; }
System.out.println("from[] lets you walk backward from the best-ending index to rebuild the actual sequence");
}
}arr = [3,1,4,1,5]
dp = [1]*5
frm = [-1]*5
for i in range(1, 5):
for j in range(i):
if arr[j] < arr[i] and dp[j]+1 > dp[i]:
dp[i] = dp[j]+1
frm[i] = j
print("from[] lets you walk backward from the best-ending index to rebuild the actual sequence")#include <stdio.h>
int main() {
int arr[] = {3,1,4,1,5};
int dp[5], from[5];
for (int i=0;i<5;i++) { dp[i]=1; from[i]=-1; }
for (int i = 1; i < 5; i++)
for (int j = 0; j < i; j++)
if (arr[j] < arr[i] && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; from[i]=j; }
printf("from[] lets you walk backward from the best-ending index to rebuild the actual sequence");
return 0;
}Login to try C/C++/Java code in the editor
Practice
LIS-style reasoning shows up in problems like finding the longest chain of nested boxes or the best sequence of non-decreasing stock trades, anywhere you need the longest valid ordering hidden inside a larger sequence.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades");
}
}print("LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades")#include <stdio.h>
int main() {
printf("LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: