Skip to main content

Longest Increasing Subsequence - LIS

Learn Longest Increasing Subsequence - LIS (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

The O(n&sup2;) DP Solution dp[i] = length of the longest increasing subsequence ENDING exactly at index i. For each i, check every earlier j: if arr[j] < arr[i] , this element could extend that subsequence.

More lessons in Dynamic Programming