Longest Increasing Subsequence
O(n^2) DP then the O(n log n) trick.
Longest Increasing Subsequence is a free Competitive Programming Academy lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Competitive Programming Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What an LIS Is
A subsequence keeps order but skips elements. The longest increasing one is the longest such run that strictly rises.
a = [3, 1, 4, 1, 5, 9, 2]Subsequence, Not Subarray
Unlike a subarray, an LIS need not be contiguous. You may jump over smaller numbers to keep the chain growing.
The O(n^2) DP State
Let dp[i] be the LIS length that ends at index i. Every element is at least a length-one subsequence by itself.
dp = [1] * nThe O(n^2) Transition
For each i, look at every earlier j. If a[j] is smaller, extend: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Read Off the Answer
The result is the largest value in the table, since the LIS can end anywhere, not only at the last index.
answer = max(dp)Why O(n^2) Can TLE
The double loop costs O(n squared). For n near 100000 that is far too slow and earns a time-limit verdict.
The Patience Idea
The faster method keeps a list of the smallest possible tail for each subsequence length, like patience sorting.
tails = []Use bisect to Place
For each number, binary-search where it fits among the tails with bisect_left, giving O(n log n) total.
from bisect import bisect_leftExtend or Replace
If the slot is past the end, append to grow the LIS. Otherwise overwrite that tail with the smaller value.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLength Lives in tails
When the scan ends, len(tails) is the LIS length. The list itself is not always the subsequence, only its length is exact.
answer = len(tails)Strict vs Non-Decreasing
For a non-decreasing variant, swap to bisect_right so equal values can extend the chain.
from bisect import bisect_rightQuick Check
Which method finds the LIS length in O(n log n)?
Recap: From n^2 to n log n
You can now solve LIS two ways. The O(n^2) DP is simple; the tails-plus-bisect method scales to large inputs and beats the time limit.
Frequently asked questions
Is the “Longest Increasing Subsequence” lesson free?
Yes — the full text of “Longest Increasing Subsequence” is free to read here on the web, and the Competitive Programming Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Competitive Programming Academy course, upgrade to CoddyKit PRO.
What will I learn in “Longest Increasing Subsequence”?
O(n^2) DP then the O(n log n) trick. You practise Competitive Programming Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Competitive Programming Academy?
No prior experience is required. Competitive Programming Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Longest Increasing Subsequence” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Competitive Programming Academy lesson?
Yes. Every Competitive Programming Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Memoization vs Tabulation
- Define State and Transition
- Climbing Stairs & Coin Combinations
- Longest Increasing Subsequence